書記が数学やるだけ#847 ランダムネットワークの性質
ランダムネットワークの性質についてまとめる。
問題
説明
1959年,ポール・エルデシュとアルフレッド・レーニは,グラフの一種であるランダムグラフを作るエルデシュ=レーニィモデルを考案した。ランダムグラフの
ランダムネットワークの次数分布は,厳密には二項分布,疎なネットワークについてはポアソン分布で表される。
ランダムネットワークの成長について,平均次数及び確率pの値により顕著に異なる性質を示す。最大連結成分は徐々に増えるのではなく,平均次数が1より小さい場合はノード数に比べゆっくりとしか増加せず,平均次数が1以上となると急激に増加する。
スモールワールド現象は,社会心理学者スタンレー・ミルグラムが1967年に行ったスモールワールド実験で検証され,その後この仮説をもとに六次の隔たりという有名なフレーズが生まれた。
1998年にダンカン・ワッツとスティーヴン・ストロガッツにより発表されたワッツ・ストロガッツモデルは,ランダムネットワークをスモールワールド性とクラスター性(クラスター係数が大きくなること)を持つよう拡張したネットワークである。
解答
ランダムネットワークについて,リンクLがある確率は二項分布で表せることから,公式より期待値を求めることができる。
次数分布は二項分布またはポアソン分布で表され,kが大きくなると急速に減少することから,ハブが存在しないことが示せる。
巨大連結成分が現れる条件について,ノードの割合を計算していく。
最後は自己無撞着方程式を解いている。計算方法は統計力学のイジングモデルも参照;
連結領域となる条件は,孤立ノード数の期待値=1から求める。
スモールワールド性について,ランダムネットワークの平均距離・直径はlnNに比例することから示される。
最後に,ランダムネットワークのクラスター係数はノードの次数に依存せず一定の値を取る。
本記事のもくじはこちら:
学習に必要な本を買います。一覧→ https://www.amazon.co.jp/hz/wishlist/ls/1XI8RCAQIKR94?ref_=wl_share