Week05 Day21

graph

내가 아는 graph의 정의는 다음과 같다.

the graph of a function f is the set of ordered pairs (x, y), where f(x) = y.¹

이산수학을 공부할 때 graph를 배웠겠지만 기억이 나질 않는다…
아래는 이산수학에서의 graph 정의이다.

a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense “related”. The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line).²

graph는 어떤 의미에서 object들의 쌍이 “관련된” object들의 집합이다.
뭔 소리지…? 내가 해석을 잘 못하는 것 같다…

강의에서 설명하는 grpah의 정의는 다음과 같다.

그래프(graph, network)는 정점(vertex, node) 집합과 간선(edge, link) 집합으로 이루어진 수학적 구조이다.

위 그림은 정점이 6개, 간선이 7개인 그래프이다.
모든 간선은 반드시 두개의 정점을 연결한다.
반드시 모든 정점이 연결되지 않는다.

복잡계(complex system)

A complex system is a system composed of many components which may interact with each other.
Examples of complex systems are Earth’s global climate, organisms, the human brain, infrastructure such as power grid, transportation or communication systems, social and economic organizations (like cities), an ecosystem, a living cell, and ultimately the entire universe.³

complex system은 서로 상호작용 많은 요소들로 구성된 system이다, 예시로 지구 기후, 인간의 뇌, 통신 시스템 등이 있다.
이런 복잡하게 상호작용하는 system을 효과적으로 표현하는 방법이 graph이다.

task related to graph

우리는 AI를 공부하고 있다.
이를 활용해 graph 관련된 문제가 뭐가 있는지 살펴본다.

• 정점 분류(node classification)
  트위터에서 리트윗을 통해 각 사용자들의 성향을 예측해본다.
  사용자가 공유한 글이나 공유받은 글 등을 통해 예측할 수 있다.
• 연결 예측(link prediction)
  페이스북 소셜 네트워크는 어떻게 진화할까? 점점 네트워크가 어떻게 변화할까? 작아질까? 커질까?
• 추천(recommendation)
  어떤 유저에게 어떤 상품을 추천해줘야 할까?
• 군집 분석(community detection)
  ⁴
  연결 관계로부터 사회적 무리(social circle)을 찾아내자.
  clustering analysis와 비슷하다.
• 랭킹(ranking) 및 정보 탐색(information retrieval)

  Information retrieval (IR) is the process of obtaining information system resources that are relevant to an information need from a collection of those resources.
  Searches can be based on full-text or other content-based indexing.
  Information retrieval is the science of searching for information in a document, searching for documents themselves, and also searching for the metadata that describes data, and for databases of texts, images or sounds.⁵

resource의 집합으로부터 요구하는 정보와 관련된 information system resources를 얻는 과정이다.
예를 들어 웹 페이지를 검색할 때 검색어와 관련된 웹 페이지를 보여주는 과정이다.

• 정보 전파(information cascading) 및 바이럴 마케팅(viral marketing)
  정보는 어떻게 전파되며 어떻게 전파를 최대로 할까?

graph type

graph를 기준에 따라 유형을 나눌 수 있다.

• 방향(direction)
  간선의 방향 유무에 따라 나눌 수 있다.
  • directed graph
  • undirected graph
• 가중치(weight)
  간선의 가중치 유무에 따라 나눌 수 있다.
  • weighted graph
  • unweighted graph
• 정점의 종류
  한 graph에 정점의 종류 수에 따라 나눌 수 있다.
  • unpartite graph
  • bipartite graph

예를 들어 e-commerce 거래 내역은 어떤 유형의 그래프일까?

`두 종류`의 정점, 구매자와 상품, 이 존재하고 구매자와 상품을 잇는 간선의 가중치를 상품에 대한 평점으로 나타낼 수 있으므로 weighted bipartite graph이다.

notation

보통 정점를 $V$, 간선들의 집합를 $E$, 그래프를 $G = (V, E)$ 로 표기한다.
정점의 이웃(neighbor)은 정점 $v$ 와 연결된 다른 정점 집합이며 $N(v)$ 혹은 $N_v$ 라고 표기한다.