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).