フクの非日常

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

複雑ネットワーク (3)

今日は複雑ネットワークの研究の足跡を追ってみます。

1736年 ケーニヒスベルクの問題
 グラフ理論の起源 レオンハルト・オイラー
 ケーニヒスベルグの街に流れる川に掛かる橋を一筆書きで歩けるか、という問題に対する証明。

1959年 エルデシュ=レーニィモデル(ERモデル)
 ランダム・グラフ
 頂点間に確率pで枝を張り、1-pで枝を張らないことをルールとしたグラフ。
 枝の存在確率は二項分布に従い、n→∞のときポアソン分布に近似することができる。
 古典的グラフと異なり、枝の分布に不均一性を持たせたことが特徴。

1960年代~1970年代 スモール・ワールド現象の研究。
 
1998年 ワッツ=ストロガッツモデル(WSモデル) 
 スモールワールドモデル=クラスター係数を大きくしたモデルの考案。

1999年 バラバシ=アルバートモデル(BAモデル) 
 スケールフリー性(ベキ則)を持つモデルの考案。

18世紀頃にグラフ理論が確立し、ランダムグラフの頃までが古典的ネットワークと位置づけられています。追って現実のネットワークが研究され、複雑ネットワークは次数分布がベキ則に従う、小さい平均頂点間距離と大きいクラスター係数を持つことがわかってきます。しかし、古典グラフではどのモデルも十分に複雑ネットワークの条件を満たしていませんでした。そこに、大きなCを持つWSモデルが提案され、複雑ネットワークの研究が飛躍的に進んだのでした。

コメント


管理者にだけ表示を許可する
 

 

トラックバック

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。