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$ は実際に成り立っていることが多い!!
- 円の面積など
- 支持する観測結果
- LiveJournal: 違う
- E-mail: 違う
- 携帯電話: OK
- 紹介論文の主張
- リンク維持のためのエネルギー制約，エントロピー最大化 → この性質が出てくる
