03. The Small World Phenomena

過去の実験

• The beacon number
• Erdos number
• [Migram'67]
  • 手紙を転送するやつ．平均 6.2 ステップ (→ 6 degrees of separation)
  • 批判
    • 収束効果 (funneling)
    • 始点がランダムでない
    • 最短路ではない，social search のようなものである
    • サンプル数が少ない
    • 参加者は外部の情報を用いたかもしれない
• Dodds, Muhamad and Watts, 2003
  • 平均距離 7

モデル

high clustering かつ small diameter を同時に実現しよう

Small-World Model [Watts-Strogats'98]

1. low-dimensional regular lattice
   • high clustering, high diameter
2. rewire: 確率 p で辺の片方の端点をランダムに動かす
   • randomness -> shortcuts

あるいは

1. square grid
2. 各頂点に 1 random edge を追加

証明．4 頂点を supernode だと思ったグラフを考えると，4-regular random graph．よって直径は O(log n)．