Looking Further Ahead Reveals An Even Smaller World
Jianyang Zeng, Wen-Jing Hsu, Ya-hong Hu · arXiv (Cornell University) · 2004
We improve Kleinberg’s original greedy routing algorithm, and show that if each node can look ahead log k log n depth of its long-range contacts, the routing path can be found with expected length of O(log n log k log n), where n is the size of the network and k is the number of long-range contacts per node. To our knowledge, this is presently the best result for routing messages in Kleinberg’s small-world models. We then extend this result to allow routing algorithms to have even more lookahead capability. Our results can cover a class of routing algorithms in the literature, and explain the so-far incoherent results by using a same framework. Key words: small-world networks, design of algorithms, distributed systems, graph algorithms, lookahead 1