1. Properties of Real-world Graphs

Degree Distribution

• $P(k)$로 나타내며 임의로 선택한 노드가 $k$의 degree를 가질 확률을 의미한다.
• $N_k$를 degree가 $k$인 노드의 수라 할 때 정규화된 히스토그램은 $P(k)=N_k/N$으로 나타낼 수 있다.

Clustering Coefficient

• $C$로 표기하며 노드 $i$가 이웃들과 어떻게 연결되어 있는지를 나타낸다.
• Degree가 $k_i$인 노드 $i$에 대해 $C_i=\cfrac {2e_i}{k_i(k_i-1)}$
• $e_i$는 노드 $i$의 이웃 노드들 간의 엣지의 수를 의미한다.
• $C=\cfrac{1}{N} \sum_{i}^{N} C_{i}$. 모든 노드에 대한 평균값으로 $C$를 정의한다.

Connectivity

• $s$로 표기하며 가장 큰 component의 크기를 나타낸다.
• 예를 들어, 99%의 노드들이 연결되어 있으면 $s$는 매우 크며 giant component라고도 부른다.
• 임의의 노드로부터 출발하며 BFS를 통해 방문한 노드를 표시한다.
• 모든 노드를 방문하면 network는 연결되어 있음을 의미하며 방문하지 않은 노드를 찾으면 BFS를 반복한다.

Path Length

• 최단경로 기준 그래프 내 노드 쌍의 최대 거리를 diameter라 한다.
• 평균 path length는 무한한 길이의 경로를 무시하기 위해 connected grpah에 대해서만 계산한다.
• $\bar{h}=\cfrac{1}{2 E_{\max }} \sum_{i, j \neq i} h_{i j}$
• $h_{ij}$는 노드 $i$와 $j$의 거리를, $E_{max}$는 엣지의 최대 개수(노드 쌍의 개수)를 의미한다.

Case Study

• 메신저 내에서 유저들의 한 달 간 활동내역에 대해 그래프로 나타낼 수 있다.
• Properties에 대한 정보를 얻을 수 있으며 이 값들이 exptected냐 surprising냐에 대해 알기 위해 모델이 필요하다.

2. Erdos-Renyi Random Graphs

• $G_{np}:$ 엣지가 독립 항등 분포(iid)의 확률 $p$를 가지는 노드 $n$에 대한 undirected graph
• $G_{nm}:$ $m$개의 엣지가 균등한 확률로 랜덤하게 뽑히는 노드 $n$에 대한 undirected graph
• 우리는 $G_{np}$에 대해서만 다룬다.

Properties of $G_{np}$

• $n,p$에 의해 그래프가 unique하게 결정되지 않는다.
• $G_{np}$는 properties로 degree distribution $P(k)$, clustering coefficient $C$, path length $h$를 가진다.

Degree Distribution

• $G_{np}$의 $P(k)$는 이항분포를 따른다.
• $n-1$개 중 선택한 $k$개는 엣지로 연결되고 나머지는 연결되지 않을 확률이 $P(k)$가 된다.

Clustering Coefficient

• $C_i=\cfrac {2e_i}{k_i(k_i-1)}$
• $G_{np}$의 엣지는 $p$의 확률로 나타나므로 이웃 노드들 간의 엣지의 수의 기댓값 $E[e_i]$는 $p\cfrac{k_i(k_i-1)}{2}$가 된다.
• 따라서, $E[C_i]==\cfrac{p \cdot k_{i}\left(k_{i}-1\right)}{k_{i}\left(k_{i}-1\right)}=p=\cfrac{\bar{k}}{n-1} \approx \cfrac{\bar{k}}{n}$

Connected Components

• $p=k/(n-1)$, average degree $k=2E/n$으로 $k=1$일 때부터 giant component가 나타난다.
• Degree $k=1-\epsilon:$ 모든 components의 크기는 $\Omega(log n)$
• Degree $k = 1+\epsilon:$ 하나의 component 크기는 $\Omega(n)$, 나머지는 $\Omega(logn)$

Expansion

• $\alpha=\min _{S \subseteq V} \cfrac{\# \text { edges leaving } S}{\min (|S|,|V \backslash S|)}$
• 그래프 $G(V,E)$에 대해 $V$의 subset $S$를 만들기 위해 끊어주어야 하는 엣지의 비율(?)이라고 이해했다.
• 분자인 #edges leaving $S$는 끊어주는 엣지의 수, $V | S$는 $S$를 뺀 나머지 subset을 의미한다.
• Expansion은 robustness의 척도가 되며 subset을 쉽게 만들 수 있는 구조면 low expansion을, 어려운 구조면 high expansion을 가진다.

• Expansion이 $\alpha$이고 $n$개의 노드를 가지는 그래프의 모든 노드 쌍에 대한 path of length는 $O((log n)/\alpha)$이다.
• 즉, path length는 노드의 개수에 비례하고 expansion에 반비례한다.
• 랜덤 그래프는 expansion이 커 $logn$의 BFS로 모든 노드를 방문할 수 있다.

• $G_{np}$의 노드들은 적은 hops만큼 떨어져 있어 $O(logn)$의 shortest path를 가진다.

Real Networks vs $G_{np}$

• 실제 그래프와 랜덤 그래프를 비교한 결과 clustering coefficient와 degree distribution이 다르다.
• 실제 그래프의 giant component는 phase transition 형태로 나타나지 않는다. (phase transition은 $k=1$을 기준으로 giant component가 등장하는 것을 의미)
• Clustering coefficient가 너무 작아 local한 구조가 나타나지 않는다는 단점도 있다.

3. The Small-World Model

Motivation

• 실제 그래프는 local한 구조를 가져 clustering coefficient가 높으면서도 낮은 diameter를 가진다.
• $G_{np}$는 낮은 clustering coefficient를 가져 이를 제대로 반영하지 못한다.

Idea

• 높은 clusering coefficient와 큰 diameter를 가지는 regular lattice graph를 interpolation 하여 그래프를 만든다.

Solution

• 이웃 노드와 2-hops인 노드를 이은 low-dimensional regular lattice를 만든다. 이 그래프는 높은 clustering coefficient와 큰 diameter를 가진다.
• 각 엣지의 endpoint를 확률 $p$에 따라 옮기는 rewiring 과정을 거친다. 이 그래프는 높은 clustering coefficient와 작은 diameter를 가진다.
• Small world networks는 regular network와 random network의 interpolation이라고 할 수 있다.

4. Kronecker Graph Model

Idea

• Object는 자기 자신의 일부와 비슷하므로 네트워크를 재귀적으로 구성할 수 있다.
• Kronecker product를 통해 self-similar 행렬을 만든다.
• Kronecker graph는 kronecker product를 초기 행렬 $K_1$에 반복적으로 행하여 만들 수 있다.
  

Stochastic Kronecker Graphs

• $N_1 \times N_1$의 확률 matrix $\theta_1$을 만든다.
• $k^{th}$ Kronecker power $\theta_k$를 계산한다.
• $\theta_k$의 entry $p_{uv}$에 따라 엣지를 생성한다.

• 위 방식은 $O(n^2)$의 시간복잡도를 가져 실제 적용에 어려움이 있다.
• 따라서, 재귀적인 구조를 활용한 더 빠른 방식을 이용한다.

Generation of Kronecker Graphs

• $\theta$로부터 normalized matrix $L$을 만든다.
  $L_{uv}=\theta_{uv}/(\sum_{op}\theta_{op})$
• $L$의 확률에 따라 가장 큰 4분할 영역 중 한 영역을 선택한다.
• 그 영역 또한 분할되어 있다면 재귀적으로 확률에 따라 선택한다.
• 단일 cell이 나올 때까지 반복하며 최종적으로 선택되면 1을 할당하여 edge를 만든다.
• 위 과정을 기대 엣지 수 $E=(a+b+c+d)^m$가 될 때까지 반복한다.
  
• Kronecker Graph가 실제 그래프와 유사함을 확인할 수 있다.

References

• Lecture 14.1: https://www.youtube.com/watch?v=OhjXpYIo9h4&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=41
• Lecture 14.2: https://www.youtube.com/watch?v=VC43S6Thwg0&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=42
• Lecture 14.3: https://www.youtube.com/watch?v=ZrDpzzVWwFs&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=43
• Lecture 14.4: https://www.youtube.com/watch?v=Xnpt8US31cQ&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=44