📂グラフ理論

バラバシ-アルバートモデル

アルゴリズム ¹

Input

リンクパラメータ$m \in \mathbb{N}$とネットワーク サイズ$N$が与えられたとする。

---

ステップ 1. 初期化

$m$個のノードを持つ初期ネットワークを構築する。特に理由がなければ、このネットワークは完全グラフとされる。

---

ステップ 2. ノードの追加

現在のノードの数が$n$個とする。ここに新たなノードを追加し、このノードは既存の各$m$個のノードとリンクが繋がる。それぞれの$k = 1 , \cdots , n$番目のノードと繋がる確率は次の通りである。 $$ p_{k} = {{ \deg k } \over { \sum_{k=1}^{n} \deg k }} $$ 重複するリンクは復元抽出を通して繋がらない。

---

ステップ 3. 繰り返し

ノードの数が$n < N$になるまでステップ 2を繰り返し、$n = N$になったらアルゴリズムを終了する。

---

Output

パレート分布 $\text{Pareto} \left( 3 \right)$の度数分布を持つスケールフリーネットワークを得る²。

説明

バラバシ・アルバートモデルは、スケールフリーネットワークを生成する最も単純で最も人気のあるアルゴリズムである。BAモデルの恐ろしい点は、複雑な式なしでも、パレート分布の本質とも言える不平等さを正確に指し示すことである。 $$ p_{k} = {{ \deg k } \over { \sum_{k=1}^{n} \deg k }} $$ この確率の意味するところは、新たなリンクが接続される理由自体を既存のリンクで見つけることである。後発の者よりも先発の者が有利であり、有利なノードはさらに有利になる。もし人気という概念がネットワークに生まれるなら、それがまさにバラバシ・アルバートネットワークだ。この理由で、時々プリファレンシャルアタッチとも呼ばれる。

コード

可視化

以下は、BAネットワークを作成し、その発展プロセスを可視化するジュリアのコードである。

@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))