読者です 読者をやめる 読者になる 読者になる

Possible Origin of Efficient Navigation in Small Worlds (PRL'11)

  • モチベーション
    • ミルグラムの実験
    • どういう構造であればこのように数ホップで辿りつけるのか
    • どういう原理に基づきそのようなネットワークが生じるのか

既存研究

  • Kleinberg small-world model (Nature'00)
    • 二点間の距離に依存したショートカットの生成確率
    • $P(u, v) \propto d(u,v)^{-\alpha}$
    • $\alpha=2$ の場合に限り,greedy search が効率的,$O(\log^2 N)$ 時間
    • $\alpha=2$ しか許されないのは現実的か?
  • 社会グループ構造モデル (Science'02)
    • 属性があり,属性によるグループのツリーみたいな感じでグループが構成されている
    • 属性ベクトルがターゲットに最も近い人を選べば探索できる

紹介論文

  • モチベーション
    • $\alpha=2$ は実際に成り立っていることが多い!!
    • 円の面積など
    • 支持する観測結果
  • 紹介論文の主張
    • リンク維持のためのエネルギー制約,エントロピー最大化 → この性質が出てくる
  • モデル
    • トーラス
    • 各辺について距離に比例したエネルギー
    • エントロピー:距離2までに現れる頻度.冗長なパス無く多数つながると嬉しい.
  • 実験1:ランダムに作ると $\alpha=2$ 的な場合がエントロピー最大になる
  • 実験2:ランダムなグラフからエントロピーの最適化を行うと $\alpha=2$ 的グラフに至る