Greedy Routing and the Algorithmic Small-World Phenomenom

摘要: The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s, was theoretically explained Kleinberg in 2000. However, today's perspective his model has several severe shortcomings that limit applicability to real-world networks. In order give a more convincing explanation of we study decentralized greedy routing flexible random graph (geometric inhomogeneous graphs) which overcomes all previous shortcomings. Apart exhibiting good properties theory, it also been extensively experimentally validated this reasonably captures In model, protocol is purely distributed as each vertex only needs know information about its direct neighbors. We prove succeeds with constant probability, and case success almost surely finds an shortest path length {\theta}(loglog n), where our bound tight including leading constant. Moreover, natural local patching methods augment backtracking do not require any global knowledge. show such can ensure probability 1 asymptotically number steps. These results address question Krioukov et al. whether there are efficient protocols for internet graph. There were promising experimental studies, but remained unsolved theoretically. Our first time rigorous analytical affirmative answer.