バラバシ-アルバートモデル
アルゴリズム 1
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)$の度数分布を持つスケールフリーネットワークを得る2。
説明
バラバシ・アルバートモデルは、スケールフリーネットワークを生成する最も単純で最も人気のあるアルゴリズムである。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))
Albert, Barabási. (2002). Statistical mechanics of complex networks. https://doi.org/10.1103/RevModPhys.74.47 ↩︎
Barabási, Albert. (1999) Emergence of Scaling in Random Networks. https://doi.org/10.1126/science.286.5439.509 ↩︎