📂그래프이론

바라바시-알버트 모델

Barabási-Albert Model

알고리즘 ¹

Input

링크 파라메터 $m \in \mathbb{N}$ 과 네트워크 사이즈 $N$ 이 주어져 있다고 하자.

---

Step 1. 초기화

노드가 $m$ 개인 최초의 네트워크를 구성한다. 별 다른 이유가 없다면 그 네트워크는 컴플리트 그래프로 주어진다.

---

Step 2. 노드 추가

현재 노드의 수가 $n$ 개라고 하자. 여기에 새로운 노드를 추가하는데, 이 노드는 기존에 있던 각 $m$ 개의 노드와 링크가 이어진다. 이 때 각각의 $k = 1 , \cdots , n$번째 노드와 이어질 확률은 다음과 같다. $$ p_{k} = {{ \deg k } \over { \sum_{k=1}^{n} \deg k }} $$ 비복원추출을 통해 중복이 되는 링크는 잇지 않는다.

---

Step 3. 반복

노드의 수가 $n < N$ 이면 Step 2를 반복하고, $n = N$ 이면 알고리즘을 끝낸다.

---

Output

차수분포가 파레토 분포 $\text{Pareto} \left( 3 \right)$ 인 스케일-프리 네트워크를 얻는다. ²

설명

바라바시-알버트 모델은 스케일-프리 네트워크를 생성하는 가장 간단한 모델인 동시에 가장 인기 있는 알고리즘이다. BA 모델의 무서운 점은 복잡한 수식 없이도 파레토 분포의 본질이라고 할 수 있는 불평등함을 정확히 가리킨다는 점이다. $$ p_{k} = {{ \deg k } \over { \sum_{k=1}^{n} \deg k }} $$ 이 확률이 의미하는 바는 바로 새로운 링크가 연결되는 이유 자체를 기존의 링크에서 찾는 것이다. 후발주자보다는 선발주자가 유리하며, 유리한 노드는 갈수록 유리해진다. 인기라는 개념이 네트워크로 태어난다면 그게 바로 바라바시 알버트 네트워크다. 이러한 이유로 가끔은 프리퍼런셜 어태치^{Preferential Attachment}라 불리기도 한다.

시각화

다음은 BA 네트워크을 생성하고 그 발달^Evolving 과정을 시각화하는 줄리아 코드다.

@time using Graphs
@time using Plots, GraphRecipes

N = 200
X = (1:N)/N .* cos.(2π * rand(N))
Y = (1:N)/N .* sin.(2π * rand(N))

G = barabasi_albert(N, 3)
graph_evolution = @animate for n ∈ 4:N
  graphplot(G[1:n], x = X[1:n], y = Y[1:n],
   curvature = 0, linealpha = 0.2, markerstrokewidth = 0, nodecolor = :gray,
   size = (300,400), nodesize = 0.1)
  xlims!(-n/N,n/N); ylims!(-n/N,n/N)
end
gif(graph_evolution, "zoomout.gif", fps = 16)