Aritalab:Lecture/NetworkBiology/Barabasi-Albert Model
(New page: ==Barabási-Albert Model== ネットワークの成長モデルとしてBarabási, Albertは以下のモデルを提唱した。(正確には初期条件が異なるが本質は同じ。...) |
|||
Line 1: | Line 1: | ||
+ | {{Lecture/Header}} | ||
+ | |||
==Barabási-Albert Model== | ==Barabási-Albert Model== | ||
Revision as of 09:50, 10 June 2010
Wiki Top | Up one level | レポートの書き方 | Arita Laboratory |
|
Barabási-Albert Model
ネットワークの成長モデルとしてBarabási, Albertは以下のモデルを提唱した。(正確には初期条件が異なるが本質は同じ。)
- 時間ステップ1において本の辺で結ばれた2頂点からスタートする。
- 単位時間毎に頂点を1つずつ追加し、既に存在する頂点と本の辺でつなぐ。新しい辺はそれぞれ確率 (ここでは頂点iの次数) で接続先を決定する。
このメカニズムを優先的選択(preferential attachment)と呼び、一般にrich gets richerメカニズムなどともいわれる。さらにBarabásiは、グラフの次数分布がべき則に従う場合をスケールフリー(scale free)ネットワークと呼びはじめた。
自然界にはべき則が普通に見られ、以下の例がよく知られている。
Network (size) | L | C | ||
---|---|---|---|---|
www (1.5 x 105) | 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 105) | 2.3 | 3.7 | 0.79 | Watts and Strogatz (1998) |
Medline (1.5 x 106) | ? | 4.6 | 0.066 | Newman (2000, 2001) |
べき分布と優先的選択は20世紀初頭にYule、20世紀半ばにもSimonらにより研究されていたが、グラフの次数分布として問題を捉えなおし、WWW等に応用した点が注目された。
べき則のパラメータについて
BAモデルからはを簡単に導出できる。 初期条件として2頂点が本のリンクで結ばれている場合、時間後には頂点数、辺数になる。 次数は時間が経つと増加していくから、という連続関数として考えてみる。
これを解くと、 ただしは頂点が追加された時間でである。 これを式変形すれば、頂点の次数がある値になる時間はであることがわかる。 次数分布を求めるには、まず頂点の次数がより大きくなる割合(累積分布関数)を求める。
左の等号は、頂点が生まれた時間が、時刻に比例値としてをかけたものよりも早ければ(小さければ)、次数がより大きくなることを示している。 しかし頂点が毎時一定量ずつ追加されることを考えると、全体サイズを1とするなら、単純にとしてよいことがわかる。
これをについて微分すると。すなわち辺の次数はに比例する。
優先的選択でない場合
新しい辺が結びつく先が一様分布に従うと仮定してみよう。
これを解いて。こちらも累積分布関数を計算してみる。
これを微分すると、すなわち辺の次数は指数的に減少することになる。
何がべき分布を作るのか
エッセンスだけ言うと、優先的選択の場合は次数の時間変化を規定する微分方程式が と、が微分値の分子に現れていた点がミソになる。これを解くとという答えが得られ(は適当な定数)、この係数1/2がを作り出す。だから異なるの値を作り出すにはにおける比の2を他にずらせればよい。
例えば
という近似を何らかの形で導出すると、に設定できる。