Barabási-Albertモデルからベキ指数を導出

次数 $k$ をもつネットワーク次数分布 $P(k)$ がベキ分布 $P(k)\sim k^{-\gamma}$ と見なせるネットワークが多く報告されている(Albert and Barabá́si, Statistical mechanics of complex networks(Reviews of Modern Physics 74, 47-97 (2002).)、Dorogovtsev and Mendes, Evolution of networks(Adv. Phys. 51, 1079 (2002))などの総合報告論文がある)。

ネットワーク頂点数平均次数ベキ指数 $\gamma$
WWW$2.03\times 10^{8}$10.462.1/2.7
インターネット150,0002.72.3
論文引用783,3398.572.5
俳優共演449,913113.42.3
英単語同一文章478,7733.982.85
ソフトウエア1,9893.982.85

Barabási-Albertモデル

成長(各ステップごとに$m$本の辺を既存グラフに接続する頂点が時間とともに増加していく)と優先選択(頂点次数の大きな頂点が辺を獲得しやすい)に基づいたBarabási-Albertモデルは、別名Rich-Get-Richerモデルともいう。

Barabási-Albertモデルで生成されるグラフのアルゴリズムを明確にしておこう。 BAモデルで生成されるネットワークは次の手順に従う。

  1. 時刻 $t=0$ での初期グラフ: 頂点数 $m_0$ からなる小さい規模の連結したグラフが与えられている。 $m_0$ は 時間経過とともに頂点 $N$ を持つ巨大グラフに成長するわけだが、$m_0 \ll N$ という相対的な意味で小さいとする。
  2. 成長: 離散時刻 $t=1,2,\dots,n \dots$ で、1つの頂点が時刻 $t-1$ で得られたグラフに追加される。
  3. 時刻 $t_i$ で追加された頂点からは定数 $m$ 本の辺が 時刻$t-1$で得られているグラフの各頂点のいずれかに接続する。 簡単のために、$m$本の辺接続においては、多重辺はが起こらないようにする。 このとき、$m$本の辺の1つが次数 $k_i$ を持つ既存グラフの頂点 $i$ に接続する確率 $\Pi_i$ は \[ \Pi_i=\frac{k_i}{\sum_{j}k_j} \] とする(優先選択:次数 $k_i$ が大きければ接続される確立が大きい)。 $\Pi_i$の分母のの和は時刻 $t-1$ で生成されたグラフの全頂点の次数についての和である。
  4. 手順 2. および 3. を目的とするグラフ規模になるまで繰り返して、グラフを成長させる。

ベキ指数を求める

Albert-László BarabásiとRéka Albertは Emergence of Scaling in Random Networksにおいて、BAモデルとして知られているスケールフリーネットワークの形成モデルを提案し、そのベキ数を連続近似による平均場の方法で理論的に求めている。

一方、 S.N. Dorogovtsev, J.F.F. Mendes, and A.N. Samukhinは Structure of growing networks: Exact solution of the Barabasi-Albert model(Phys. Rev. Lett. 85, 4633-4636 (2000))で、BAモデルにおいて離散時刻 $t_i$ で生成された頂点 $i$ が時刻 $t$ で次数 $k$ も持つ確率 $p(k,t_i, t)$ に関するマスター方程式を解くことによってベキ指数を求めた。

そのいずれかの方法によっても、各ステップで生成される頂点が接続する辺の本数 $m$ や初期ネットワークに依存することなく、ベキ指数は $\gamma=3$ と計算される。

平均場近似の方法

Albert-László BarabásiとRéka Albertが Emergence of Scaling in Random Networksで考えられた方法である。

時刻 $t=0$ で頂点数 $m_0$ で、以降、離散時刻ごとに1つずつ $m$ 本の辺を既存グラフに優先選択的に接続される頂点が新たに加えられる。 時刻 $t_i$ で頂点が加えられたとき、その頂点次数 $k_i$ の時間変化 $k_i(t)$ を考える。 付け加えられた当初は $m$ 本の辺を持つため

\[ k_i(t_i)= m \]

である。 時刻 $t$ における頂点 $i$ への(あらたに付加された頂点からの)辺結合確率が $\Pi_i(t)$ より、時刻 $t$ における頂点 $i$ の次数の増分の期待知は (あらたに付加された頂点は常に $m$本の辺を有するために)$m\Pi_i$ である。

離散時間間隔 $\Delta t=1$であるのだが、 頂点 $i$ が誕生した時間 $t_i$ からすっと後の時間 $t$ ($t-t_i \gg \Delta t$)と考えれば、次数分布の時間変化 $k_i(t)$ も、十分大きな $t$ においては $k_i(t)\gg m$ となって、連続的に見なせるようになる。 すなわり、$k_i$ の増分は

\[ \frac{dk_i}{dt}=m\Pi_i \]

と表される(平均場近似)。 時刻 $t$ のグラフの総次数 $\sum_j k_j$ は、時刻 $t$ の頂点数が$t$ であることから、 各頂点は $m$本の辺を持っていることを考慮すれば

\[ \sum_jk_j=m_0+2mt \]

である。$t\gg t_i$ とすれば、$\sum_jk_j\approx 2mt$、つまり$\Pi_i\approx 2mt$ となって

\[ \frac{dk_i}{dt}=\frac{k_i}{2t} \]

になる。 これを初期条件 $k_i(t_i)=m$ のもとで解くと次を得る。

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

これを書き換えて、時刻$t$で次数$k$を持つ頂点はいつの時間 $t_k$ に発生したかと見なすことができる。

\[ t_k=\left(\frac{m}{k}\right)^2 t \]

この事実は、時刻 $t$ において次数が $k$ より小さい頂点の総数 $N_{\text{$k$より少}}(t)$は、時刻 $t_k$ よりも後に発生したわけであるあので、

\[ N_{\text{$k$より少}}(t)=t-t_k=t-\left(\frac{m}{k}\right)^2 t \]

時刻 $t$ におけるグラフの頂点数 $N(t)$ 、頂点の次数分布 $P(k)$ とすると、頂点の次数は初期の $m$ から増加していくので、時刻 $t$ において、次数が $k$ 以下の頂点の数は

\[ N(t)\int_m^kP(k')dk' \]

である。 $N(t)=m_0 + t\approx t$ とみなせば次の関係を得る。

\[ \int_m^kP(k')dk'=1-\left(\frac{m}{k}\right)^2 \]

両辺を $k$ で微分すると、次数分布 $P(k)$ が得られる。

\[ P(k)\propto m^2 k^{-3} \]

この結果は、スケールフリーネットワークのBAモデルでは、次数分布 $P(k)$ のベキ指数は、出現する頂点が接続する辺の数 $m$ や 初期グラフの頂点数 $m_0$ に無関係に $\gamma=3$ であることが示された。 また、次数分布の係数は $m^2$ に比例することもわかる。

マスター方程式の方法

S.N. Dorogovtsev, J.F.F. Mendes, and A.N. Samukhinが Structure of growing networks: Exact solution of the Barabasi-Albert model(Phys. Rev. Lett. 85, 4633-4636 (2000))で考えた方法を紹介しよう(Dorogovtsev and Mendes, Evolution of networks(Adv. Phys. 51, 1079 (2002), 節IX.A. Baraáasi-Albert model and the idea of preferential linking)。

頂点 $s$(時刻 $t_s=s$ に生まれた)が時刻 $t$($s