📂그래프이론

바라바시-알버트 모델

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)

구현

가중치를 주고 샘플링하는 함수 randw()을 포함해서 패키지에 의존하지 않고 바라바시-알버트 모델을 만드는 함수 barabasi_albert()를 구현했다.

function randw(item, weight)
    @assert length(item) == length(weight) "length mismatch"
    @assert any(weight .> 0) "all weights are zero"
    @assert all(weight .≥ 0) "there is a negative weight"
    
    Σ = sum(weight)
    if !isone(Σ)
        weight = weight ./ Σ
    end
    return item[findfirst(rand() .≤ cumsum(weight))]
end
randw(['a', 'b', 'c'], [1,2])
randw(['a', 'b', 'c'], [0,0,0])
randw(['a', 'b', 'c'], [1,2,-1])
randw(['a', 'b', 'c'], [1,2,3])
abc = [randw(['a', 'b', 'c'], [1,2,3]) for _ in 1:6000]
count.([abc .== 'a', abc .== 'b', abc .== 'c'])

function randw(item, weight, n; replace = true)
    @assert n ≤ length(item) "n = $n is larger than the length of item = $(length(item))"

    while true
        sample = [randw(item, weight) for _ in 1:n]
        if (length(unique(sample)) == n) || replace
            return sample
        end
    end
end
randw(-10:-1, 1:10, 5)
randw(-10:-1, 1:10, 5, replace = false)

function barabasi_albert(N, m = 1)
    G = [setdiff(1:m, k) for k in 1:m]
    for new in (m+1):N
        idxs = randw(1:(new-1), length.(G), m, replace = false)
        push!(G, idxs)
        push!.(G[idxs], new)
    end
    return G
end

ba = barabasi_albert(1000, 3)
degree = length.(ba)

using Plots
histogram(degree)
histogram(degree, xscale = :log10, yscale = :log10, xticks = 10.0 .^(-0:0.5:2), xlims = extrema(degree))