[CS224W] Lecture 2 : Measuring Networks, and Random Graph Model

Stanford의 강의 CS224W(2018 Fall)를 정리한 포스트입니다.

코스 전체에서 다루는 주제입니다.

Topic # Lectures
Course Introduction and Structure of Graphs 1
Measuring Networks, and Random Graph Model 2
Link Analysis: PageRank 3
Network Construction, Inference, and Deconvolution 4
Motifs and Graphlets 5
Community Structure in Networks 6
Community Detection: Spectral Clustering 7
Link Prediction 8
Graph Representation Learning 9
Network Effects and Cascading Behavior 10-11
Influence Maximization & Outbreak Detection 12-13
Power-laws and Network Robustness 14
Network Centrality 15
Message Passing and Node Classification 16
Network Evolution 17
Knowledge Graphs and Metapaths 18
Graph Convolutional Networks 19


Network Properties: How to Measure a Network?

Networks(Graphs)에 대한 정보를 나타내는 네가지 방법에 대해 논의한다.

  1. Degree distribution $P(k)$
  2. Path length $h$
  3. Clustering coefficient $C$
  4. Connected components $s$

Degree Distribution

CS224W-02-01 Degree distribution은 node들의 degree를 histogram으로 표현한 것이다. 위의 표를 보면 degree가 1인 노드가 전체노드들 중에서 대략 60%를 차지한다는 것을 알 수 있다.

Paths in a Graph

CS224W-02-02 path는 서로 연결되어있는 node들의 시퀀스다. Distance는 두 node사이의 가장 짧은 path의 길이다. 연결되어 있지 않은 node사이의 distance는 infinity다. Directed graph에서는 path 와 distance둘다 arrow방향에 따라 계산되며 distance는 symmetric하지않다 ( $ \text{h}_{B,C} \neq \text{h}_{C,B} $ 일 수 있다). Network의 diameter는 node 사이의 distance중 가장 큰 값으로 결정된다. graph가 disconnected 되어있다면 diameter는 infinity다. Average path length는 가능한 path들의 평균이다. 이때 finite path만 계산한다. $E_{max}$ 는 최대 edge 수이고, normalize term으로써 적용한다.

Clustering Coefficient

CS224W-02-03 Clustering coefficient는 social network anlysis에서 주로 사용되었다. 각 노드가 얼마나 community의 중심에 있는지를 알려주는 지표라고 볼 수 있다. Clustering coefficient $C_i$가 0에 가까울 수록 주변 노드들이 해당 노드를 통해서만 연결되어 있는 것이고, 1에 가까울 수록 해당 노드 없이도 주변 노드끼리 충분히 연결되어 있는 것이다. 수식에서 $k_i$는 주변 노드들의 수(degree)고, $e_i$는 주변 노드끼리의 연결 edge 수다. A, F, G 노드같은 경우는 0으로 계산된다.

Connectivity

CS224W-02-04 그래프에서 가장 큼지막한 덩어리의 사이즈를 의미한다. 일반적으로 disconnected graph에서 분석된다. 랜덤한 노드에서 시작해서 너비 우선 탐색을 수행한다. 만약 모든 노드가 탐색되면 해당 graph는 connected graph다. 만약 탐색되지 않은 노드가 있다면 그 노드부터 다시 너비우선 탐색을 수행한다.

Let’s measure $P(k), h, C$ on a real-world network!

CS224W-02-05 실제 네트워크를 위에서 설명한 방법대로 표현해보자. MSN Messenger는 사용자간 텍스트를 주고 받을 수 있는 서비스다. 사용자간 관계를 오른쪽 그림처럼 graph로 표현할 수 있다.

CS224W-02-06 이 때, 사용자 node degree distribution을 log scale로 표현하면 (1) 처럼 나타난다. degree가 작은 사용자가 많고, degree가 큰 사용자는 상대적으로 적다는 것을 확인할 수 있다. (2)는 사용자 cluster coefficient를 나타낸다. (3)에서는 connectivity를 나타내는데, 대부분의 노드가 큰 덩어리로 연결되어 있음을 알 수 있다. (4)를 보면, 이 network에서는 상대적으로 distance가 작은 path들이 많다는 것을 알 수 있다.

Erdos-Renyi Random Graph Model

CS224W-02-07 Random graph model은 총 $n$개의 node로 이루어져있고 두 node 사이의 edge가 일정 확률 $p$ 로 생성된 graph를 만들어내는 model을 의미한다. 이때 생성되는 graph를 $G_{n,p}$ 로 표기한다. 만약 probability $p$가 아닌 총 edge 갯수 $m$ 으로 나타낸다면 $G_{n,m}$ 으로 표기한다. 이러한 graph의 특성 degree distribubtion, clustering coefficient, path, connectivity 는 어떻게 계산될까? 실제 데이터와는 어떠한 차이가 있을까?

CS224W-02-08

  • Degree distribution : edge가 일정 확률로 생기기 때문에 bionomial distribution을 따른다. graph가 무한히 커지면 node들의 degree는 균일해진다. (variance가 0으로 수렴한다.)
  • Clustering coefficient : graph가 무한히 커지면 clustering coefficient 는 0으로 수렴한다.

CS224W-02-09 Expansion $\alpha$는 graph 에서 임의의 subset $S$를 구했을 때, $S$에서 나가는 edge의 수를 ‘subset’과 ‘이외의 set’의 크기중 작은 것으로 나누었을때 최솟값을 의미한다. Expansion은 subset에서 edge가 퍼져나가는 정도를 나타내며, $\min(|S|,|V\S|)$ 로 나누어주는 것은 graph 전체의 절반보다 작은 subset으로 normalize 하기 위해서다 (subset을 뽑는다는 것이 graph를 양분 한다는 의미니까 뒤집었을때도 같은 값을 갖기 위해). Expansion은 robustness를 측정하는 지표로 볼 수 있다. 즉, $l$개의 노드를 disconnect하고자 할 때, 최소 몇개의 edge를 끊어야 하는지 알수 있게 해준다. Expansion값이 작으면 subset간의 edge가 별로 없는 것이고, 크면 subset간의 edge가 많은 것이다.

CS224W-02-10 처음 $s$개의 노드를 정하고 각각의 노드와 $(\alpha\cdot S)$ edges로 연결된 노드들을 구한다. 그 다음, 새롭게 연결된 노드들까지 포함하여 $S’$ 노드들을 다시 하나의 subset으로 보고 $(\alpha\cdot S’)$ edges로 연결된 노드들을 구한다. 이렇게 모든 노드들을 방문할 때까지 반복하여 path를 구할 수 있다. path length는 $O((\log n)/\alpha)$ 다. 우측 그림에서 노드 수가 증가할때 shortest path는 log 함수 형태로 증가함을 볼 수 있다.

CS224W-02-11 Edge가 생성될 확률 $p$에 따라 random graph의 종류가 바뀐다. 우선, $p=0$이면 edge없이 노드들만 있는 graph다. $p=1$이면 모든 노드들이 연결되어 있는 complete graph다. $p=\frac{1}{n-1}$ 일때 average degree가 1이 되어 giant component가 나타나기 시작한다. $p=\frac{1-\epsilon}{n-1}$ 일때는 모든 component 들이 $\Omega(\log n)$ 크기로 옹기종기 소분되어 있고, $p=\frac{1+\epsilon}{n-1}$ 일때는 하나의 큰 component ($\Omega(n)$ 크기)와 작은 component ($\Omega(\log n)$ 크기)로 이루어져있다.

CS224W-02-12 실제 network와 random network와 비교.

  • Degree distribution : 실제 Network는 분포가 쏠려있는데, random graph에서는 binomial 반복에 의한 gaussian distribution을 따른다.
  • Average path length : $n=180M$이고 $\log n$을 구해보면, 대강 비슷하다고 볼 수 있다.
  • Average clustering coefficient : 많은 차이가 난다. -> 바로 아래에서 비슷하게 만들어주는 방법을 다룬다.
  • Largest connected component : 실제 Network에서는 99% 노드가 하나의 Giant component로 연결되어 있고, random graph에서도 $\bar{k}>1$일 때 Giant component가 존재한다. 여기서 $\bar{k} \approx 14$이므로 둘다 Giant component가 존재한다.

Random graph와 실제 Network는 일정 부분은 비슷하지만, 그렇다고 완전 유사하다고는 할 수 없다. Random graph는 일종의 reference로 사용할 수 있는데, 실제 Network가 random graph와 비교했을 때, 크게 다른 부분이 있다면 그건 해당 Network의 특성이 되는 것이다.

The Small-World Model

CS224W-02-13 Milgram의 실험은 다음과 같다. 각각 지역에서 300명을 모아 stoch-broker에게 오직 친구들만 통해 편지를 전달하게끔 한다. 그 후 몇 스텝만에 도달하는지 분석하는 실험이다. 그 결과, 64개의 편지가 도달했고, 평균 스텝은 6.2였다. 이것이 얼마나 특별한 것인지 보기 위해 간단한 계산을 해보자. 한명당 평균 100명의 친구가 있다고 가정하면, 5 step만 거쳐도 10 billion의 사람에게 편지를 전달 할 수 있다. 6 step은 이런 단순 계산으로 치면 전혀 빠른 전달이 아니다. 그러나 이런 단순 분석에서 놓친 것은 clustering이다. 위에서 살펴봤듯, 실제 network와 random graph는 Avg. path length는 대강 비슷하지만 clustering coefficient에서 많은 차이가 났다.

CS224W-02-14

  • 실제 Network (ex. facebook)에서는 전혀 동떨어진 사람과 관계(친구신청)를 하지는 않고, 끼리끼리 뭉쳐있는 경우가 많다. Clustering은 locality를 의미한다.
  • 반면에 random graph에서는 전혀 상관 없어 보이는 노드에도 edge가 일정 확률로 연결되어 있다. 이러한 연결은 shortcuts를 가능하게 한다. 즉, 나와 동떨어진 사람도 몇다리 안거쳐도 편지를 금방 받을 수 있다.

강한 locality 와 shortcuts를 동시에 갖게 하려면 어떻게 할까? 이에 대한 답이 Small-World Model이다.

CS224W-02-15 Small-World Model은 두가지 요소로 이루어져 있다.

  1. Low-dimensional regular lattice 를 생성한다. 이는 주변노드끼리만 이어져있는 네트워크를 의미한다. 즉, High clustering이고 따라서 High diameter이다.
  2. Rewire : 주변 노드와의 연결을 일정 확률 $p$로 끊고, 아무 노드와 연결한다. 이런 연결이 생길 때마다 shortcut이 생기는 것이다. 즉, diameter가 점점 작아진다. 반면 clustering은 점점 낮아질 것이다.

2번의 $p$에 따라서 적정한 small-world graph를 만들 수 있다. 이는 좀더 real network와 가까운 특성(high clustering, low diameter)을 갖게끔 만들어준다. 그러나 degree distribution은 여전히 real network와는 다르다.