Barabási–Albert 모델의 degree distribution 유도: Continuum approximation#

1. 문제 설정#

Barabási–Albert, 즉 BA 모델은 preferential attachment를 통해 scale-free network가 어떻게 생기는지를 설명하는 대표적인 네트워크 성장 모델이다.

핵심 아이디어는 간단하다.

이미 연결이 많은 노드는 새 노드로부터 더 많은 연결을 받을 가능성이 높다.

즉, “부익부” 구조가 네트워크 성장 과정 안에 들어 있다.

2. BA 모델의 성장 규칙#

BA 모델은 보통 다음과 같이 정의된다.

1. 초기에는 작은 네트워크가 있다.
2. 매 시간마다 새로운 노드 하나가 네트워크에 추가된다.
3. 새 노드는 기존 노드들 중 m개와 연결된다.
4. 기존 노드 i가 새 링크를 받을 확률은 그 노드의 degree k_i에 비례한다.

즉,

$$ \Pi_i = \frac{k_i}{\sum_j k_j} $$

여기서

• $\Pi_i$: 새 노드가 기존 노드 $i$에 연결될 확률
• $k_i$: 노드 $i$의 degree
• $\sum_j k_j$: 전체 네트워크의 degree 합

3. 전체 degree 합#

무방향 네트워크에서 전체 degree 합은 edge 수의 두 배이다.

BA 모델에서는 매 시간마다 새 노드가 m개의 edge를 추가한다.

따라서 시간 $t$가 충분히 크면 edge 수는 대략

$$ mt $$

이고, 전체 degree 합은

$$ \sum_j k_j \approx 2mt $$

이 된다.

따라서 preferential attachment 확률은

$$ \Pi_i = \frac{k_i}{2mt} $$

로 쓸 수 있다.

4. 한 노드의 degree가 시간에 따라 어떻게 증가하는가?#

이제 특정 노드 $i$를 보자.

노드 $i$가 시간 $t_i$에 네트워크에 들어왔다고 하자.

BA 모델에서는 새 노드가 들어올 때 처음부터 m개의 링크를 가지므로,

$$ k_i(t_i) = m $$

이다.

시간이 지나면서 이 노드는 새로 들어오는 노드들로부터 링크를 받을 수 있다.

한 시간 step마다 새 노드는 m개의 링크를 만든다. 그중 하나가 노드 $i$에 연결될 확률은 $\Pi_i$이다.

따라서 노드 $i$의 degree 증가율은

$$ \frac{dk_i}{dt} = m \Pi_i $$

이다.

앞에서 구한 $\Pi_i = k_i / 2mt$를 대입하면,

$$ \frac{dk_i}{dt} = m \frac{k_i}{2mt} $$

m이 약분되어

$$ \frac{dk_i}{dt} = \frac{k_i}{2t} $$

이 된다.

이 식이 continuum approximation의 핵심이다.

5. 미분방정식 풀기#

우리는 다음 미분방정식을 풀면 된다.

$$ \frac{dk_i}{dt} = \frac{k_i}{2t} $$

양변을 분리하면,

$$ \frac{dk_i}{k_i} = \frac{dt}{2t} $$

양변을 적분하면,

$$ \ln k_i = \frac{1}{2}\ln t + C $$

따라서

$$ k_i(t) = C’ t^{1/2} $$

이다.

이제 초기조건을 사용한다.

노드 $i$는 시간 $t_i$에 들어왔고, 그때 degree는 $m$이다.

$$ k_i(t_i) = m $$

그러므로

$$ m = C’ t_i^{1/2} $$

따라서

$$ C’ = m t_i^{-1/2} $$

이를 다시 대입하면,

$$ k_i(t) = m \left(\frac{t}{t_i}\right)^{1/2} $$

즉, 노드 $i$의 degree는 시간이 지남에 따라 다음처럼 증가한다.

$$ k_i(t) = m \sqrt{\frac{t}{t_i}} $$

6. 이 식의 직관#

$$ k_i(t) = m \sqrt{\frac{t}{t_i}} $$

이 식은 중요한 직관을 준다.

• $t_i$가 작을수록, 즉 일찍 들어온 노드일수록 degree가 크다.
• 늦게 들어온 노드는 성장할 시간이 적기 때문에 degree가 작다.
• 하지만 degree는 $t/t_i$에 비례해서 선형으로 증가하는 것이 아니라 제곱근으로 증가한다.

즉, early mover advantage가 있지만 무한히 압도적인 방식은 아니다.

7. Degree distribution으로 바꾸기#

우리가 원하는 것은 개별 노드의 degree 성장식이 아니라 전체 네트워크의 degree distribution이다.

즉,

$$ P(k) $$

를 구하고 싶다.

앞에서 얻은 식은

$$ k_i(t) = m \left(\frac{t}{t_i}\right)^{1/2} $$

이다.

이 식을 $t_i$에 대해 풀면,

$$ k_i(t) > k $$

라는 조건은 다음과 같다.

$$ m \left(\frac{t}{t_i}\right)^{1/2} > k $$

양변을 정리하면,

$$ \left(\frac{t}{t_i}\right)^{1/2} > \frac{k}{m} $$

양변을 제곱하면,

$$ \frac{t}{t_i} > \frac{k^2}{m^2} $$

따라서

$$ t_i < \frac{m^2 t}{k^2} $$

이 된다.

즉, degree가 $k$보다 큰 노드들은 충분히 일찍 들어온 노드들이다.

8. $t_i$의 분포#

BA 모델에서는 매 시간마다 노드가 하나씩 들어온다.

따라서 노드의 등장 시간 $t_i$는 대략 $[0,t]$ 구간에 균등하게 분포한다고 볼 수 있다.

그러므로

$$ P(k_i(t) > k) = P\left(t_i < \frac{m^2 t}{k^2}\right) $$

이고, $t_i$가 균등분포이므로

$$ P\left(t_i < \frac{m^2 t}{k^2}\right) = \frac{m^2 t / k^2}{t} $$

따라서

$$ P(k_i(t) > k) = \frac{m^2}{k^2} $$

이것은 누적분포의 꼬리, 즉 complementary cumulative distribution이다.

보통 다음처럼 쓴다.

$$ P(K > k) \sim k^{-2} $$

9. 누적분포에서 확률밀도분포로#

우리가 흔히 말하는 degree distribution은

$$ P(k) $$

이다.

앞에서 얻은 것은

$$ P(K > k) \sim k^{-2} $$

이다.

연속 근사에서는 확률밀도는 누적분포를 미분해서 얻을 수 있다.

$$ P(k) = -\frac{d}{dk}P(K > k) $$

따라서

$$ P(k) \sim -\frac{d}{dk}k^{-2} $$

이고,

$$ P(k) \sim k^{-3} $$

즉 BA 모델의 degree distribution은

$$ P(k) \sim k^{-3} $$

이 된다.

10. 결론#

Continuum approximation을 통해 BA 모델의 degree distribution을 유도하면 다음과 같은 결과를 얻는다.

$$ P(k) \sim k^{-3} $$

즉, BA 모델은 power-law degree distribution을 만든다.

이때 exponent는

$$ \gamma = 3 $$

이다.

따라서 BA 모델은 scale-free network의 대표적인 생성 메커니즘으로 이해된다.

11. 핵심 흐름 요약#

전체 유도 과정은 다음과 같이 요약할 수 있다.

1. Preferential attachment를 가정한다.

$$ \Pi_i = \frac{k_i}{\sum_j k_j} $$

2. 전체 degree 합은 대략 $2mt$이다.

$$ \sum_j k_j \approx 2mt $$

3. 노드 $i$의 degree 증가율은 다음과 같다.

$$ \frac{dk_i}{dt} = m \frac{k_i}{2mt} = \frac{k_i}{2t} $$

4. 미분방정식을 풀면,

$$ k_i(t) = m \left(\frac{t}{t_i}\right)^{1/2} $$

5. degree가 $k$보다 클 조건은

$$ t_i < \frac{m^2 t}{k^2} $$

6. 등장 시간 $t_i$가 균등분포라고 보면,

$$ P(K > k) \sim k^{-2} $$

7. 이를 미분하면,

$$ P(k) \sim k^{-3} $$

12. Continuum approximation의 의미#

여기서 continuum approximation은 원래 이산적인 네트워크 성장 과정을 연속적인 미분방정식으로 근사하는 방법이다.

실제로 degree는 정수이고 시간도 discrete step으로 증가한다.

하지만 노드 수가 충분히 크고 degree 변화가 평균적으로 부드럽다고 보면,

$$ \frac{dk_i}{dt} $$

와 같은 연속적인 증가율로 근사할 수 있다.

이 방식은 정확한 해는 아니지만, BA 모델이 왜 power-law 분포를 만드는지 직관적으로 보여주는 가장 간단한 유도법이다.

13. 한 줄 요약#

BA 모델에서는 먼저 들어온 노드가 preferential attachment 덕분에 더 많은 링크를 얻고, 이 성장 과정이 누적되면서 degree distribution이

$$ P(k) \sim k^{-3} $$

인 scale-free network가 만들어진다.