<CS224W> Lecture 14. Traditional Generative Models for Graphs

kimkj38·2022년 4월 27일
0

CS224W

목록 보기
14/17
post-thumbnail

1. Properties of Real-world Graphs

Degree Distribution

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

Clustering Coefficient

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

Connectivity

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

Path Length

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

Case Study

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

2. Erdos-Renyi Random Graphs

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

Properties of GnpG_{np}

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

Degree Distribution

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

Clustering Coefficient

  • Ci=2eiki(ki1)C_i=\cfrac {2e_i}{k_i(k_i-1)}
  • GnpG_{np}의 엣지는 pp의 확률로 나타나므로 이웃 노드들 간의 엣지의 수의 기댓값 E[ei]E[e_i]pki(ki1)2p\cfrac{k_i(k_i-1)}{2}가 된다.
  • 따라서, E[Ci]==pki(ki1)ki(ki1)=p=kˉn1kˉnE[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/(n1)p=k/(n-1), average degree k=2E/nk=2E/n으로 k=1k=1일 때부터 giant component가 나타난다.
  • Degree k=1ϵ:k=1-\epsilon: 모든 components의 크기는 Ω(logn)\Omega(log n)
  • Degree k=1+ϵ:k = 1+\epsilon: 하나의 component 크기는 Ω(n)\Omega(n), 나머지는 Ω(logn)\Omega(logn)

Expansion

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

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

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

Real Networks vs GnpG_{np}

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

3. The Small-World Model

Motivation

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

Idea

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

Solution

  • 이웃 노드와 2-hops인 노드를 이은 low-dimensional regular lattice를 만든다. 이 그래프는 높은 clustering coefficient와 큰 diameter를 가진다.
  • 각 엣지의 endpoint를 확률 pp에 따라 옮기는 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를 초기 행렬 K1K_1에 반복적으로 행하여 만들 수 있다.

Stochastic Kronecker Graphs

  • N1×N1N_1 \times N_1의 확률 matrix θ1\theta_1을 만든다.
  • kthk^{th} Kronecker power θk\theta_k를 계산한다.
  • θk\theta_k의 entry puvp_{uv}에 따라 엣지를 생성한다.
  • 위 방식은 O(n2)O(n^2)의 시간복잡도를 가져 실제 적용에 어려움이 있다.
  • 따라서, 재귀적인 구조를 활용한 더 빠른 방식을 이용한다.

Generation of Kronecker Graphs

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

References

0개의 댓글