書記が数学やるだけ#847 ランダムネットワークの性質

ランダムネットワークの性質についてまとめる。

問題

説明

1959年，ポール・エルデシュとアルフレッド・レーニは，グラフの一種であるランダムグラフを作るエルデシュ＝レーニィモデルを考案した。ランダムグラフの

ランダムネットワークの次数分布は，厳密には二項分布，疎なネットワークについてはポアソン分布で表される。

ランダムネットワークの成長について，平均次数及び確率pの値により顕著に異なる性質を示す。最大連結成分は徐々に増えるのではなく，平均次数が1より小さい場合はノード数に比べゆっくりとしか増加せず，平均次数が1以上となると急激に増加する。

スモールワールド現象は，社会心理学者スタンレー・ミルグラムが1967年に行ったスモールワールド実験で検証され，その後この仮説をもとに六次の隔たりという有名なフレーズが生まれた。

1998年にダンカン・ワッツとスティーヴン・ストロガッツにより発表されたワッツ・ストロガッツモデルは，ランダムネットワークをスモールワールド性とクラスター性（クラスター係数が大きくなること）を持つよう拡張したネットワークである。

解答

ランダムネットワークについて，リンクLがある確率は二項分布で表せることから，公式より期待値を求めることができる。

次数分布は二項分布またはポアソン分布で表され，kが大きくなると急速に減少することから，ハブが存在しないことが示せる。

巨大連結成分が現れる条件について，ノードの割合を計算していく。

最後は自己無撞着方程式を解いている。計算方法は統計力学のイジングモデルも参照；

連結領域となる条件は，孤立ノード数の期待値=1から求める。

スモールワールド性について，ランダムネットワークの平均距離・直径はlnNに比例することから示される。

最後に，ランダムネットワークのクラスター係数はノードの次数に依存せず一定の値を取る。

本記事のもくじはこちら：