Chapter2. Properties of Networks, Random Graph Models

12기 박진혁

Network Properties : How to Measure a Network

Key Networks Properties : 보통 이 4가지 요소로 그래프를 평가한다.

Degree Distribution (각 Node의 Degree의 확률분포)
Path length
Cluster Coefficient
Connected components

(1) Degree Distribution : 어떤 그래프가 있을 때, 우리가 여기서 랜덤으로 Node를 뽑았을 때, 그 Node의 degree가 k일 확률들의 분

(2) PATH : 각 Node 들이 연결된 Sequence

그림1 에서 Path는 ACD, ACDBDE, 등등 다양한 path가 존재한다. ACDBDE처럼 한 node를 여러번 지날수도 있으며, 교차로 지나갈 수도 있다.

*PATH에서 파생된 개념

Distance : 우리가 직관적으로 Path라고 하면 생각나는 것이 Distance라고 생각하면 된다. 여러 Path중 Node(i) -> Node(j)로 가는 Shortest Path를 Distance라고 하며, 길이 없을 때는 Path는 보통 무한대라고 정의 된다. (Directed 그래프의 경우, 화살표를 따라서만 길을 갈 수 있다. 그림2에서 A -> C로 가는 Path는 1이 아닌 2가되고, D에서 C로가는 Path는 무한대로 정의할 수 있다)

Diameter(직경): 어떤 그래프에서 Path의 최대값. 가장 먼 두 node의 거리를 나타내주는 값이라고 생각하면 되는데, 그래프가 원의 형태일경우 이게 직경이라고 생각할 수 있다. 그러나, 실처럼 연결된 그래프는 직경이 엄청 커지게 되는 등 왜곡이 잘 발생되므로, 썩 Useful하지 않다고 한다.
Avearge Path length (평균 경로): Path length의 평균값(무한대인 Path는 무시한다)

(3) Clustering Coefficient : 어떤 노드 i에 대해 얼마나 이 노드와 연결된 노드들끼리 잘 연결돼 있는가를 나타낸 지수

계산 예시) 그림3에 두 번째 그림을 보면 i는 총 4개의 node로 연결이 돼있으며, 이 4개의 node끼리 연결될 수 있는 경우의 수는 4*3 = 12개이다. 여기서 서로 연결된 edge의 개수는 3개이므로 3*2/12 = 1/2이 되는 것이다

(4) Connectivity : 가장 큰 Component의 크

그림4를 보면 저 제일 위 덩어리가 가장 큰 것을 알 수 있는데 이 것의 크기가 Connectivity가 된다. (한 node를 잡고 BFS를 반복해서 연결된 노드를 모두 지나고, 모든 노드를 지났다면 안 지난 node하나를 선택해서 또 BFS를 반복해 크기를 구한다.)

MSN Messenger 예시(뒤에 또 나올예정)

ErdosRenyi Random Graph Model

랜덤 Graph의 두 가지 종류 :

(1) G_np : 어떤 n개의 node가 있을 때 임의의 두 node사이에 Edge가 존재할 확률이 p로 iid인 것

(2)G_nm : n개의 node, m개의 edge가 있을 때, 그 m개의 edge가 uniform하게 random으로 존재

G_np에 대해 4가지 properties를 비교해보

(1) P(k) & Clustering Coefficient

(2) Path (Diameter)

Expansion alpha : 전체 노드를 두 부분, A B로 나눴을 때, 더 작은 부분을 A라하면, A -> B로가는 edge의 수의 최소값을 Expansion alpha라고 한다.

Diameter가 커지는 속도는, 일반적으로 log(n)이라고 하는데 이 것은 아래 설명이 잘 나와있어 첨부합니다.

앞서 살펴본 바를 토대로 Random Graph가 가지고 있는 문제점들을 살펴보도록 하자. 먼저 Average path length는 l¯≃lognlogc로 표현이 되며 이것은 곧, random graph는 n의 값에 비례하여 path length가 늘어나는 것이 아니라 log scale로 증가한다는 것을 알 수 있다. 즉, n이 매우 크더라도 path는 그에 비해 매우 짧다는 것을 알 수 있다. 이것은 실제 대부분의 네트워크들에서도 나타나는 현상이다. 반면 clustering coefficient는 cn으로 표현이 되며 n의 값이 증가할 수록 떨어지는 것을 알 수 있는데, 실제 network들이 n이 커지더라도 높은 clustering coefficient를 유지한다는 점에서 현실과 잘 맞지 않는다는 것을 알 수 있다. 마지막으로 Degree distribution을 살펴보게 되면, random graph에서의 degree distribution은 P(k)≃e−cckk!로 근사가 되는데, 실제 네트워크에서 관측되는 distribution은 P(k)≃k−γ 와 같은 power distribution이다. 따라서 이 역시 잘 맞지 않는다는 것을 알 수 있다.

출처 : http://sanghyukchun.github.io/50/

(3) Giant Component (Connectivity)

Giant Component의 Fraction 역시 logarithm하게 증가하는 것을 알 수 있는데, avg degree가 1이 되지않으면 (사실상 한 군데 이상 연결돼있지 않다는 의미이다) 0에 수렴한다(원래 log를 생각하면 음수가 되어야하니..) http://sanghyukchun.github.io/50/ 위에 링크했던 곳인데 여기보면 증명도 상세하게 나와있다 ㅎㅎ 스터디 때 시간 남으면 같이 유도해봅시다!

Real World와 비교해보면, 랜덤그래프의 경우 n이 커짐에 따라 Clustering Coef가 아주 낮아지는 점, Degree distribution의 분포가 아주 다르다는 점 때문에 real world를 잘 묘사할 수 없게 된다.