{"html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fiwiwi.hatenadiary.jp%2Fentry%2F2013%2F04%2F11%2F221516\" title=\"Possible Origin of Ef\ufb01cient Navigation in Small Worlds (PRL&#39;11) - iwiwi \u5099\u5fd8\u9332\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","height":"190","author_url":"https://blog.hatena.ne.jp/iwiwi/","image_url":null,"provider_name":"Hatena Blog","width":"100%","provider_url":"https://hatena.blog","published":"2013-04-11 22:15:16","blog_url":"https://iwiwi.hatenadiary.jp/","version":"1.0","title":"Possible Origin of Ef\ufb01cient Navigation in Small Worlds (PRL'11)","url":"https://iwiwi.hatenadiary.jp/entry/2013/04/11/221516","type":"rich","categories":[],"blog_title":"iwiwi \u5099\u5fd8\u9332","description":"\u30e2\u30c1\u30d9\u30fc\u30b7\u30e7\u30f3 \u30df\u30eb\u30b0\u30e9\u30e0\u306e\u5b9f\u9a13 \u3069\u3046\u3044\u3046\u69cb\u9020\u3067\u3042\u308c\u3070\u3053\u306e\u3088\u3046\u306b\u6570\u30db\u30c3\u30d7\u3067\u8fbf\u308a\u3064\u3051\u308b\u306e\u304b \u3069\u3046\u3044\u3046\u539f\u7406\u306b\u57fa\u3065\u304d\u305d\u306e\u3088\u3046\u306a\u30cd\u30c3\u30c8\u30ef\u30fc\u30af\u304c\u751f\u3058\u308b\u306e\u304b \u65e2\u5b58\u7814\u7a76 Kleinberg small-world model (Nature'00) \u4e8c\u70b9\u9593\u306e\u8ddd\u96e2\u306b\u4f9d\u5b58\u3057\u305f\u30b7\u30e7\u30fc\u30c8\u30ab\u30c3\u30c8\u306e\u751f\u6210\u78ba\u7387 $P(u, v) \\propto d(u,v)^{-\\alpha}$ $\\alpha=2$ \u306e\u5834\u5408\u306b\u9650\u308a\uff0cgreedy search \u304c\u52b9\u7387\u7684\uff0c$O(\\log^2 N)$ \u6642\u9593 $\\alpha=2$ \u3057\u304b\u8a31\u3055\u308c\u306a\u3044\u306e\u306f\u73fe\u5b9f\u7684\u304b\uff1f \u793e\u4f1a\u30b0\u30eb\u30fc\u30d7\u69cb\u9020\u30e2\u30c7\u30eb (Science'02) \u5c5e\u6027\u304c\u3042\u308a\uff0c\u5c5e\u6027\u306b\u3088\u308b\u30b0\u30eb\u30fc\u30d7\u306e\u30c4\u30ea\u2026","author_name":"iwiwi"}