CS224W - 02.Properties of Networks, Random Graph Models

CS224W의 2주차 강의, Properteis of Networks, Random Graphs Models를 정리한 내용입니다.
1. Network Properties: How to Measure a Network
2. Let’s measure these properties on real-world networks!
3. Erdős–Rényi Random Graph Model
4. The Small-World Model
5. Kronecker Graph Model

Properties of Networks, Random Graph Models

Network Properties: How to Measure a Network

네트워크는 네 가지의 특성(Property)를 지닌다.
Property 표기
Degree Distribution P(k)
Path Length h
Clustering Coefficient C
Connected Components s

Property	표기
Degree Distribution	P(k)
Path Length	h
Clustering Coefficient	C
Connected Components	s

특성1. Degree Distribution

Degree(차수): 임의로 노드를 택했을 때, 그 노드가 Degree k를 가질 확률
다음과 같은 그래프에 대해 Degree Distribution의 히스토그램을 그려볼 수 있음.
- 역시 방향 그래프는 전입, 전출 차수 각각에 대해 Degree Distribution을 갖게 될 것.

특성2. Path Length

Path: 노드들의 Sequence
- Path라는 개념은 같은 edge를 여러 번 방문해도 상관 없음.
Distance (= Shortest Path, Geodesic)
- 무방향 그래프의 경우
  한 노드에서 다른 특정 노드까지 갈 수 있는 경로 중 가장 짧은 경로
  만약 두 노드가 연결되어 있지 않다면, Distance = Infinity로 정의
- 방향 그래프의 경우
  반드시 arrow의 방향을 따라서 path를 설정해야.
  때문에 방향 그래프에서는 symmetric하지 않다.
Diameter
해당 그래프가 얼마나 큰가?
한 그래프 상에서의 모든 노드 쌍들 사이에서의 maximum (shortest path) distance
- 실제 그래프에서는 그다지 유용하지 않음
- Upper bound의 관점에서 바라보면 될 듯.
Average Path Length
- 대상: Connected Graph or Strongly Connected Directed Graph
- 정의
- 대부분의 경우, Average Path Length에 있어서, 연결된 노드들만 고려함. (Infinite Length Path는 무시)

특성3. Clustering Coefficient

대상: 무방향 그래프(Undirected Graphs)
“어떤 노드 i의 neighbor들이 서로 어떻게 연결 되어 있나?”
표기:
- 예를 들어, 첫번째 그림
  k_i는 4 ∵ 노드 i는 degree가 4이기 때문.
  e_i는 6 ∵ 노드 i와 연결된 4개의 노드 간에는, 6개의 Edge가 존재하기 때문.
- Average Clustering Coefficient: 모든 노드들마다의 Clustering Coefficient를 평균낸 것에 불과.
예시
- 해석: ‘대략 1/3의 random node들이 서로 연결되어 있다.’
- 예상컨대, Social Network의 경우에는 Clustering Coefficient가 클 것.

특성4. Connectivity

Largest connected component의 크기
Largest Component = Giant Component

Let’s measure these properties on real-world networks!

이제 이 4가지 특성을 실세계에 적용시켜보자.
(Degree Distribution, Path Length, Clustering Coefficient, Connected Components)
MSN Messenger의 사례
- 이 유저들의 Communication Network

특성1. Degree Distribution in MSN example

GNN02-9

근데 이 그래프는 너무 useless 해보임. 여기서 어떤 insight를 얻을 수 있겠어…
- Idea: x, y axis 모두에 log scale을 적용해보자.
‘아, 대다수의 사람들은 small degree를 갖고 있으며, degrees는 놀라울 정도로 skewed되어 있구나!’

특성2. Path Length in MSN example

X-Axis인 Distance는 Linear scale로, Y-Axis인 path 수는 log scale로
‘아, 대다수의 노드들은 서로 가까이에 위치해 있구나.’

특성3. Clustering Coefficient in MSN example

‘아, C=0.1140으로, 어떤 사람은 다른 지인의 지인들 중 11% 정도를 함께 아는 구나.’

특성4. Connectivity in MSN example

log-log scale
결국 MSN의 사례에 대하여 4가지 Property를 요약해보면,

와 같이 요약해볼 수 있음.
- 이에 대해 다음과 같은 궁금증이 생김.
```
이 숫자들이 큰 건지 작은 건지 모르겠다.  
이 숫자들을 보고 놀라야하는 건가?  
```
  → 모델의 필요성

몇 가지 모델을 소개할 것
```
- Erdős–Rényi Random Graph Model  
- The Small-World Model  
- Kronecker Graph Model  
```
- 이 모델들도 결국에는 관심이 되는 네트워크의 비교 기준이 되는 것이기 때문에 4가지 Property에 대해 조사하게 될 것.

Erdős–Rényi Random Graph Model

두 가지 variant가 있는데 그 중 를 사용할 것. (이하 gnp로 명명)
- 그래프: not uniquely defined by n, p (Random Process)
  = 똑같은 n,p라도 i.i.d with probability p이기 때문에 수많은 이형들이 생겨날 수 있음.

특성1. Degree Distribution in Erdős–Rényi Random Graph Model

gnp의 Degree Distribution은 이항분포를 따른다.
- 여기서 n-1: 하나의 노드와 연결될 수 있는 노드의 개수는 n-1개
- 문제점 하나 발견! (MSN 데이터는 결코 bell-shaped가 아니다.)

특성2. Path Length in Erdős–Rényi Random Graph Model

Expansion의 개념 등장
이 모델은 굉장히 커질 수는 있지만 노드들은 단지 a few hops apart일 뿐임.

특성3. Clustering Coefficient in Erdős–Rényi Random Graph Model

GNN02-20
$E(C_i) = \frac{2}{k_i(k_i-1)}E(e_i) = \frac{2}{k_i(k_i-1)} \times p \ \frac{k_i(k_i-1)}{2} = p$

특성4. Connectivity in Erdős–Rényi Random Graph Model

GNN02-21

x축: avg degree, y축: fraction of nodes in largest CC

MSN과의 비교

GNN02-22

Avg. path length, Largest Connected Components의 관점에서는 MSN case가 그다지 놀랄만한 사실은 아니다.
- gnp의 특성2 -> O(logn): 그래프 크기보다 exponentially smaller
  -> MSN의 6.6이란 수치는 그닥 놀랍지 않음.
- gnp의 특성4 -> k bar가 1보다만 크면 GCC가 존재하는데, k bar=14래
  -> MSN의 99%라는 수치 또한 그닥 놀랍지 않음.
다만, Degree distribution과 Avg.clustering Coefficient의 관점에서 gnp로부터의 결과는 MSN과 거리가 멀다.
- 실세계의 Network는 결코 gnp처럼 random하지 않다.
  -> 이 말인 즉슨, 관심 네트워크에서의 4가지의 특성이 gnp에서의 4가지 특성 수치와 결과가 유사하다면, 그 네트워크는 random한 특성을 지닌 네트워크라 할 수 있을 것
- 하지만 gnp 모델은 reference model이 된다는 점에서 그 의의를 지님.

The Small-World Model

문제의식: “현실세계의 네트워크는 아마도 ‘High clustering & Short Paths’일 것인데, 이를 반영할 수 있는 모델을 만들 수는 없을까?”

(뭔가 이 중간쯤 되는 그런 그래프 모델을 찾고 싶다.)
- 위에서 확인한 바, gnp 모델과 실제 MSN 네트워크의 Avg. Clustering Coefficient는 7자리수(7 orders of magnitude)만큼의 큰 차이가 남.
The Small-World Model
High clustering과 small diameter를 동시에 획득하는 모델
- 형성 방법?
  1. Start with a low-dimensional regular rattice
    - 굉장히 큰 clustering coefficient를 가진다. (이 경우: 1)
  2. Rewire: Introduce randomness(“shortcuts”)
    - 모든 edge들을 p의 확률로 다른 random node로 rewire
결과
The Small-World Model을 통해 Clustering Coefficient의 문제는 해결했는데, 아직 degree distribution의 문제는 해결하지 못함.

Kronecker Graph Model

소제목: ‘Generating large realistic graphs’
Ideation: ‘네트워크가 Self-similarity의 특성을 갖고 있음에 착안하여, Recursive하게 네트워크 구조를 형성해보면 어떨까?’
- ‘Self-similarity’: 한 Object는 Object의 특정 부분과 닮아있다.
- Kronecker Product: Self-similar matrices를 generate하는 방법

Kronecker Graphs

GNN02-28

Kronecker Product

GNN02-29

Kronecker Graph는 initiator matrix K1에 대해 Kronecker product를 iterate 하여 graph들의 sequence들을 키워나감으로써 형성됨.
- 근데 위 그래프를 보고 드는 생각
  현실과는 맞지 않는데? 아. 그렇다면 Kronecker Graphs를 Stochastic한 관점에서 접근해보아야겠다!

Stochastic Kronecker Graphs

GNN02-32

또 문제의식 발생: “Node의 수가 많아지면 Operation의 수 또한 많아질텐데? (Quadratic in the number of nodes) 조금 더 빨리 generate 할 수 있는 방법은 없을까?”
-> “Recursive 구조를 사용하자.”

Faster way

GNN02-33

‘1’이 바로 앞의 ‘cell-by-cell product’의 예라면,
‘2’는 ‘Re-insertion’을 통해 더 빠른 연산을 가능하게 하는 방법.
두 방법이 똑같은 결과를 내는데, 2가 연산 속도가 훨씬 빠르다 -> Then, why not?
알고리즘
결론적으로, 실세계 데이터의 분석 결과와 Kronecker 모델로부터의 결과는 굉장히 similar

요약해보자면, 분석의 대상이 되는 네트워크는 네 가지 특성을 가지고, 이 네 가지 특성을 수치화할 수 있다. 이 수치를 해석하려면 (이 수치가 큰지, 작은지, 유의미한 것인지) 결국 baseline이 필요한 건데, 우리는 기본적인 ‘모델’을 baseline으로 상정하고 관심이 되는 네트워크에 대해 해석을 함. 세 가지 그래프 모델을 소개 (Erdős–Rényi Random Graph Model, The Small-World Model, Kronecker Graph Model)

References

CS224W: Properties of Networks, Random Graph Models