[Social Network] Social Network Generation

Social Network Generation

Social network 그래프를 생성하는 모델은 크게 2가지가 존재한다.

• Random graph (erdos-renyi model)
  • 랜덤한 방식으로 그래프를 생성한다.
  • node들이 미리 주어져있고 random selection으로 edge가 생성된다고 가정한다.
  • 그러나 현실의 social network와는 다른 모습을 보인다.
• scale-free network
  • power law distribution의 형태로 그래프를 생성한다.
  • 평균과 표준편차의 의미가 별로 없게 되는 형태이다.
  • social network의 모습도 scal-free network의 형태를 따른다.

 

왜 Social Network는 Random Graph가 아닌가?

World wide web의 link = 6, N ~ $10^9$임이 밝혀졌다.

 

Random Graph를 따를 경우 (= Normal Distribution을 따를 경우)

Random graph는 정규분포를 따르기 때문에 정규분포임을 가정하게 되면

$P(k=500) ~ 10^{-99}$ → $N(k=500) ~ 10^{-90}$이어야 한다.

즉 k=500인 node는 없어야 한다.

그러나 실제로는 1000개 이상이 존재함이 밝혀졌다.

 

Power Law Distribution을 따를 경우

k와 P(k)는 log의 형태를 가지므로 $P(k=500) ~ 10^{-6}$이 되고 $N(k=500) ~ 10^3$이 된다.

이는 실제 네트워크의 형태와 유사하다.

 

distribution of world wide web

 

Random Graph vs. Scale-Free Network

인터넷 네트워크는 scale-free network가 random graph에 비해 공격에 강인할 수 있다.(robust)

link가 다르게 분포되어있고 link가 작은 node의 수가 훨씬 많기 때문에 uniform하게 생성됬을 경우에 비해 끊기는 link 수가 적기 때문이다.

 

그러나 hub(in-link가 많은 노드)가 공격당할 경우 scale-free network는 쉽게 망가질 수 있다.

 

따라서 hub를 중심으로 보안 계획을 세움으로써 네트워크 사업자는 더 적은 비용으로 더 robust한 네트워크를 구성할 수 있다.

random network vs scale-free network

 

---

Scale-free Network

노드의 수가 고정되어있지 않고 새로운 노드가 들어와서 계속해서 확장되는 네트워크이다.

 

Link의 확장 : 빈익빈 부익부

Node 사이의 link가 uniform(random)하게 존재하지 않는다.

새로운 노드가 들어왔을 때 해당 node는 더 많은 link를 가진 노드와 연결될 가능성이 높다.

→ 빈익빈 부익부

 

예를 들어, 논문 인용의 경우 새로운 논문은 인용된적 없는 논문에 비해 더 많이 인용된 논문을 인용할 가능성이 높다.

 

생성 방법

'k = 몇 개의 out-link를 가질 것인가' 가 주어졌을 때,

두 개의 서로 연결된 vertex가 존재한다고 가정하자.

 

i = 3 ~ N까지

1. $1 \leq j < i$에 대해 $d(j)$ = 점 j의 degree, $Z = \Sigma d(j)$를 계산한다.
2. $k$개의 edge(link)를 가지는 새로운 vertex $i$는 각 vertex에 $\frac{d(j)}{Z} = \frac{d(j)}{\Sigma d(j)}$의 확률로 연결된다. → 더 많은 link를 가진 node에 붙기 쉽다.

 

Degree의 Distribution

Degree는 power law distribution은 따르지만 k 값에 따라 달라진다.

* k = 각 node는 몇 개의 out-link를 가질 것인가

 

k 값이 클 수록 high degree node가 발생할 가능성이 크다.

즉 더 heavy-tailed의 형태를 가지기 쉽다.