[CS224w, 2018] Network Representation

 

Directed & Undirected 

(Left) Directed graph (Right) Undirected graph (Stanford CS224W, 2018)

위 그림의 왼쪽 빨간색 그래프는 무방향 그래프(undirected graph)이다. link는 symmetric, reciprocal 하다는 특징이 있다. 예를 들어 친구관계(서로 친구관계), 또는 협업(collaboration, 방향성이 없음)을 표현할 때 사용될 수 있다.

 

오른쪽 그림의 녹색 그래프는 방향 그래프(directed graph)이다. link는 종종 arc라고도 불린다. phone call이다 SNS에서의 follow 등을 표현할 수 있다.

 

Node degrees (노드 차수)

일반적으로 노드의 이웃하는 edge의 개수를 의미하고, $k$를 이용하여 표기한다.

Undirected Graph

노드 $i$의 이웃하는 edge의 개수를 $k_i$라 한다. 아래 그림의 경우, $A$의 차수는 $k_A=4$이다.

average degree: $\bar{k} = \cfrac{1}{N}\sum_{i=1}^{N} k_i = \cfrac{2E}{N}$

Undirected graph (Stanford CS224W, 2018)

 

Directed Graph

directed graph에서 edge는 방향을 갖기 때문에 노드 입장에서 in-degree(진입차수)와 out-degree(진출차수) 2가지가 존재한다. 아래 예시에서 $k_C^{in}=2$, $k_C^{out}=1$ 이다. undirected의 경우처럼 $k$를 표기할 수 있는데 이 경우 in-degree와 out-degree의 합으로 표기한다. (즉, $k_C=3$)

또한 $\bar{k} = \cfrac{E}{N}$이고 $\overline{k^{in}} = \overline{k^{out}}$ 이다.

Directed graph (Stanford CS224W, 2018)

 

Bipartite graph (이분 그래프)

노드 집합이 두개의 분리집합(disjoint set) $U$와 $V$로 나뉘고, 모든 link가 서로 다른 종류의 노드끼리 연결된 그래프를 bipartite graph라고 한다. Author-Paper, Actor-Movie, User-Movie, 레시피-재료 등의 관계를 표현할 수 있다.

(이분그래프에서, 같은 노드집합 내의 노드끼리는 link가 있으면 안된다. 아래 그래프를 예로 들면, $U$의 원소인 $A$와 $B$ 사이에 link가 있으면 안된다.)

Example of Bipartite graph (Stanford CS224W, 2018)

Folded / Projected Bipartite Graph

Folded Bipartite Graph (Stanford CS224W, 2018)

Representing Graphs

Adjacency Matrix (인접 행렬)

$N$개의 노드를 갖는 그래프는 $N \times N$ 모양의 인접행렬 $A$로 나타낼 수 있다.

이때 entry $A_{ij}$는 $i$에서 $j$로 연결된 link(edge)가 있으면 $1$이고, 그렇지 않으면 $0$이다.

인접행렬의 인덱스가 각각 source와 destination을 의미하기 때문에, undirected graph의 $A$는 symmetric하지만, directed graph의 $A$는 non-symmetric하다.

Example: Two graphs (Stanford Cs224W, 2018)

\[ A_{\text{undirected}} = \begin{bmatrix} 0&1&0&1 \\ 1&0&0&1 \\ 0&0&0&1 \\ 1&1&1&0 \end{bmatrix} \quad A_{\text{directed}} = \begin{bmatrix} 0&0&0&1 \\ 1&0&0&0 \\ 0&0&0&0 \\ 0&1&1&0 \end{bmatrix}  \]

 

※ Adjacency Matrix는 매우 sparse하다. 

Edge List (간선 리스트)

graph를 edge의 집합으로 표현하는 방법이다.

Example Graph (Stanford CS224W, 2018)

위와 같은 그래프의 경우, $G = \{ (2,3), (2,4), (3,2), (3,4), (4,2), (4,5), (5,1) \} $

Adjacency List (인접 리스트)

그래프가 비교적 크고(large), 희소하면(sparce), edge list보다 adjacency list가 더 효과적이다.

빠르게 어떤 노드의 이웃노드를 파악할 수 있다.

위의 예시를 그대로 인접리스트로 표현하면 다음과 같다.

\begin{align} 1 &: \\ 2&: 3,4 \\ 3&: 2,4 \\ 4&: 5 \\ 5&: 1,2 \end{align}

 

Positive and Negative Weights

trust/untrust의 관계를 표현할 때는 각각 positive, negative weight를 부여할 수 있다.

이 영역은 아직도 연구 중이며, 어떻게 negative를 전파(propagate)시키는 방법이 관건이다.

예를 들어, SNS에서 부정적 감정이 전파시키기, enemy의 enemy는 friend인지 파악하는 것 등이 연구 주제가 될 수 있다.

 

반응형