[CS224w, 2018] Network Properties and Real World

 

Key properties

주로 4가지 성질에 대해서 알아보자. degree distribution($P(k)$), path length($h$), clustering coefficient($C$), connected components($s$)에 대해 살펴보자.

 

1. Degree distribution

노드 차수(degree)의 분포를 $P(k)$로 부른다. 이때 $k$는 degree를 의미한다. 전체 노드 개수를 $N$, 노드 차수가 $k$인 노드의 개수를 $N_k$라 하면 $P(k) = \cfrac{N_k}{N}$ 이다.

Example graph and its degree distribution (Stanford CS224W, 2018)

2. Paths in a graph

path는 노드의 수열(sequence of nodes)을 나타낸다. 이때 차례로 나타나는 노드는 이전 노드와 연결되어있어야 한다.

path는 self intersect가 가능하여 중복되는 edge를 거쳐갈 수 있다. 예를 들어, 아래 그래프에서 ACBDCDEG 역시 path이다.

방향 그래프에서는 edge의 방향대로만 path가 생성된다.

Example graph (Stanford CS224W, 2018)

Distance (shortest path)

distance는 두 노드의 최단거리이다. 두 노드가 연결되어 있지 않다면, 거리는 $\infty$로 정의한다.

방향 그래프에서는 두 노드의 거리가 항상 symmetric하지 않다.

Example of Distance (Stanford CS224W, 2018)

Diameter

그래프의 모든 shortest path 중에서 가장 거리가 큰 것을 diameter라 한다.

\[ \text{Diameter} = \max h_{ij} \]

 

Average path length

connected graph (방향그래프의 경우, strongly connected component)에 대하여 평균 path 길이는 다음과 같다.

\[ \bar{h} = \cfrac{1}{2 E_{\text{max}}} \sum_{i \neq j} h_{ij} \]

 

Cluster Coefficient

어떤 노드의 이웃 노드들이 얼마나 연결되어있는지에 대한 계수이다.

노드 $i$의 차수를 $k_i$라 하자. 그리도 $e_i$를 $i$의 이웃노드끼리의 edge 개수라 하면

\[ C_i = \cfrac{2 e_i}{k_i (k_i - 1)} \in [0, 1] \]

 

average cluster coefficient는 다음과 같다.

\[ \bar{C} = \cfrac{1}{N} \sum_{i=1}^{N} C_i \]

 

Cluster Coefficient (Stanford CS224W, 2018)

 

Connectivity

그래프의 연결요소(connected component) 중에서 가장 큰 것을 Giant component라 한다.

아래 그래프에서 Giant component는 $\{ A,B,C,D \}$가 된다.

너비우선탐색(Breadth First Search, BFS)로 찾을 수 있다.

Connectivity (Stanford CS224W, 2018)

Network Properties in Real-World Network

이제 실제 세상에서 만들어지는 그래프가 어떤 특징을 갖는지 살펴보자.

먼저 MSN messenger에서 생성된 그래프 데이터(180M nodes, 1.3B edges)로 위에서 살펴본 property를 살펴보자.

Degree distribution (Stanford CS224W, 2018)

위 그래프는 동일한 데이터의 분포를 나타낸 것이다. 분포가 heavy skewed하기 때문에 log-log plot으로 시각화하였다.

Clustering Coefficient (Stanford CS224W, 2018)

Connected Components (Stanford CS224W, 2018)

Diameter of WCC (Stanford CS224W, 2018)

average path length는 $6$ 정도 되며, 심지어 90%의 노드는 8-hop 이내에 모두 도달가능하다. (What a small world!)

 

Summary of MSN Graph (Stanford CS224W, 2018)

PPI Dataset에서도 동일한 특징을 살펴본 것이다. (Stanford CS224W, 2018)

그렇다면 이러한 특징/속성들에 우리는 놀라워야 할까? 아니면 당연히 기대되는 것인가?

아래 설명할 랜덤 그래프와 비교하여 확인해보자.

 

Random Graph Model

1960년에 초기 그래프 연구자 Erdös와 Renyi가 발표한 논문에 근거한 random graph model이다. (On the evolution of the random graphs)

여러가지 변형이 있지만, 여기서는 $n$개의 노드에 임의의 edge $(u,v)$가 연결될 확률이 $p$인 랜덤 그래프를 $G_{n,p}$라 하자. $n$과 $p$가 같다고 해서 항상 같은 그래프를 생성하지 않는다.

Random graph model cannot uniquely determine the graph (Stanford CS224W, 2018)

Degree distribution

$G_{n,p}$의 degree distribution은 이항분포(binomial distribution)을 따른다. 따라서

\[ P(k) = \dbinom{n-1}{k}p^{k} (1-p)^{n-1-k} \]

 

Cluster Coefficient

노드 $i$에 대하여 $e_i$의 기댓값을 구하면 $E[e_i] = \cfrac{k_i (k_i-1)}{2}p$이다. 따라서

\[ E[C] = \cfrac{p k_i (k_i - 1)}{k_i (k_i - 1)} = p = \cfrac{\bar{k}}{n-1} \approx \cfrac{\bar{k}}{n} \]

따라서  random graph model에서 $C$는 매우 작은 값을 갖는다.

 

Evolution of Random Graph

random graph model은 edge가 생길 확률 $p$에 따라서 그래프의 모양이 바뀐다.

Simulation Experiment (Stanford CS224W, 2018)

Comparing to Real-Network

MSN Network and Random Graph Model (Stanford CS224W, 2018)

degree distribution과 clustering coefficient의 경우 real-world network에서 매우 특이한 값을 갖는다는 것을 알 수 있다.