バラバーシ・アルベルト・モデル

ウィキペディア小見出し辞書

バラバーシ・アルベルト・モデル（バラバシ・アルバートモデル）

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/26 11:37 UTC 版)

「複雑ネットワーク」の記事における「バラバーシ・アルベルト・モデル（バラバシ・アルバートモデル）」の解説

1999年、バラバーシ・アルベルト・ラースロー（アルバート＝ラズロ・バラバシ）とアルベルト・レーカ（英語版）はスケールフリー性を持つグラフの数学モデルを考案し、「バラバーシ・アルベルト・モデル（バラバシ・アルバートモデル）」（BAモデル）と呼ばれる。バラバーシ・アルベルト・モデル（バラバシ・アルバートモデル）では次のようなアルゴリズムでグラフを生成する。やはり、極めて単純なアルゴリズムである。 m 個の頂点からなる完全グラフ Kmをスタートとする。 新しい頂点を1個追加する。その頂点から、すでに存在している m 個の頂点に対して辺を張る。このとき、辺が張られる確率は、それぞれの頂点のその時点での次数 k に比例するものとする。 2を、頂点が所定の数になるまで繰り返す。 バラバーシ・アルベルト・モデル（バラバシ・アルバートモデル）では、既存の次数の大きな頂点に対して新しい辺が高い確率で加わってゆき、その頂点がハブへと成長してゆく（右の図では一番上にある頂点がハブに相当する）。このモデルでは頂点の次数分布は p(k) = 2m(m+1) / [k(k+1)(k+2)] ∝ k-3 となり γ = -3 のスケールフリー性を満たす。モデルはランダムグラフと似たところもあるので、平均最短距離は L ∝ log n となりスモールワールド性をも満たす。 バラバーシ・アルベルト・モデル（バラバシ・アルバートモデル）の弱点は、クラスター係数が0に近い小さな値となり、クラスター性を満たさないことである。だがその後、これらの研究をさらに発展させる形で、単純なアルゴリズムでありながら「スケールフリー性」「スモールワールド性」「クラスター性」という現実世界のネットワークの3つの特徴全てを満たすようなモデルが発表されている。