Greedy Routing and the Algorithmic Small-World Phenomenom
Greedy Routing and the Algorithmic Small-World Phenomenom
复制标题
DOI：
10.1016/j.jcss.2021.11.003
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
K. Bringmann;Ralph Keusch;J. Lengler;Yannic Maus;A. R. Molla
中科院分区：
文献类型：
--
作者：
K. Bringmann;Ralph Keusch;J. Lengler;Yannic Maus;A. R. Molla
算法小世界现象由 Milgram 在 60 年代凭经验建立[1]，并由 Kleinberg 在 2000 年从理论上解释[2]。然而，从今天的角度来看，他的模型有几个严重的缺点，限制了其在现实世界网络中的适用性。为了给出更有说服力的解释，我们研究了随机图模型（几何非齐次随机图）中的去中心化贪婪路由，该模型克服了之前的所有缺点。我们证明贪婪路由以恒定概率成功，并且在成功的情况下几乎肯定会找到长度为 θ (log log n) 且拉伸为 1+ o (1) 的几乎最短路径。此外，自然的局部修补方法确保成功概率为 1，同时保持相同的拉伸。这些结果还解决了互联网图是否存在有效的本地路由协议的问题。尽管实验研究很有希望，但这个问题在理论上仍未得到解决。我们第一次对经过彻底验证的互联网图模型给出了严格、肯定的答案。
The algorithmic small-world phenomenon, empirically established by Milgram in the 60 s [1], was theoretically explained by Kleinberg in 2000 [2]. However, from today's perspective his model has several severe shortcomings that limit the applicability to real-world networks. In order to give a more convincing explanation, we study decentralized greedy routing in a random graph model (geometric inhomogeneous random graphs) which overcomes all previous shortcomings. We prove that greedy routing succeeds with constant probability, and in case of success almost surely finds an almost shortest path of length Θ (log log n), with stretch 1+ o (1). Moreover, natural local patching methods ensure success probability 1, while maintaining the same stretch. These results also address the question whether there are efficient local routing protocols for the internet graph. Despite promising experimental studies the question remained unsolved theoretically. We give for the first time a rigorous, affirmative answer for a thoroughly validated model of the internet graph.