Aritalab:Lecture/NetworkBiology/Barabasi-Albert Model

Barabási-Albert Model

ネットワークの成長モデルとしてBarabási, Albertは以下のモデルを提唱した。(正確には初期条件が異なるが本質は同じ。）

時間ステップ1において $m$ 本の辺で結ばれた2頂点からスタートする。
単位時間毎に頂点を1つずつ追加し、既に存在する頂点と $m$ 本の辺でつなぐ。新しい辺はそれぞれ確率 $\textstyle p_i = k_i / \sum_j k_j$ (ここで $k_i$ は頂点iの次数) で接続先を決定する。

このメカニズムを優先的選択(preferential attachment)と呼び、一般にrich gets richerメカニズムなどともいわれる。さらにBarabásiは、グラフの次数分布がべき則 $p(k) = k^{-\gamma}$ に従う場合をスケールフリー(scale free)ネットワークと呼びはじめた。

自然界にはべき則が普通に見られ、以下の例がよく知られている。

Network (size)	$\gamma$	L	C
www (1.5 x 10⁵)	$\gamma_{in}=2.1, \gamma_{out}=2.7$	3.1	0.11	Barabasi and Albert (1999)
Internet (3000-6000)	2.16	3.7	0.18-0.3	Faloutous et al. (1999)
Movie actor (2.2 x 10⁵)	2.3	3.7	0.79	Watts and Strogatz (1998)
Medline (1.5 x 10⁶)	?	4.6	0.066	Newman (2000, 2001)

べき分布と優先的選択は20世紀初頭にYule、20世紀半ばにもSimonらにより研究されていたが、グラフの次数分布として問題を捉えなおし、WWW等に応用した点が注目された。

べき則のパラメータ $\gamma$ について

BAモデルからは $\gamma = 3$ を簡単に導出できる。初期条件として2頂点が $m$ 本のリンクで結ばれている場合、 $t$ 時間後には頂点数 $t+1$ 、辺数 $mt$ になる。次数 $k_i$ は時間が経つと増加していくから、 $k_i(t)$ という連続関数として考えてみる。

$\frac{\partial k_i}{\partial t} = m \frac{k_i}{\sum_j k_j} = \frac{k_i}{2t}$

これを解くと $\textstyle k_i(t) = m(t/t_i)^{1/2}$ 、ただし $t_i$ は頂点 $i$ が追加された時間で $k_i(t_i)=m$ である。これを式変形すれば、頂点の次数がある値 $x$ になる時間は $t=t_i(x/m)^2$ であることがわかる。次数分布を求めるには、まず頂点の次数が $k$ より大きくなる割合（累積分布関数）を求める。

$Pr(k_i(t) > k) = Pr(t_i < t(\frac{m}{k})^2) = (\frac{m}{k})^2$

左の等号は、頂点 $i$ が生まれた時間 $t_i$ が、時刻 $t$ に比例値として $(m/k)^2$ をかけたものよりも早ければ（小さければ）、次数が $k$ より大きくなることを示している。しかし頂点が毎時一定量ずつ追加されることを考えると、全体サイズを1とするなら、単純に $(\frac{m}{k})^2$ としてよいことがわかる。

これを $k$ について微分すると $P(k_i(t) = k) = -2m^2/k^3$ 。すなわち辺の次数は $k^{-3}$ に比例する。

優先的選択でない場合

新しい辺が結びつく先が一様分布に従うと仮定してみよう。

$\frac{\partial k_i}{\partial t} = m/(n-1) = m/t$

これを解いて $k_i(t) = m(\log(\frac{t}{t_i})+1)$ 。こちらも累積分布関数を計算してみる。

$P(k_i(t) > k) = P(t_i < t(1-\frac{1}{exp(k/m - 1)}) = 1-exp(1-(k/m))$

これを微分すると $P(k_i(t)=k)=exp(-k/m)/m$ 、すなわち辺の次数は指数的に減少することになる。

何がべき分布を作るのか

エッセンスだけ言うと、優先的選択の場合は次数の時間変化を規定する微分方程式が $\textstyle \frac{dy}{dx} = \frac{y}{2x}$ と、 $y$ が微分値の分子に現れていた点がミソになる。これを解くと $y=cx^{1/2}$ という答えが得られ（ $c$ は適当な定数）、この係数1/2が $\gamma=-3$ を作り出す。だから異なる $\gamma$ の値を作り出すには $y/2x$ における比の2を他にずらせればよい。