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