Greedy pathlengths and small world graphs

AbstractWe use matrix analysis to study a cycle plus random, uniform shortcuts—the classic small world model. For such graphs, in addition to the usual edge and vertex information there is an underlying metric that determines distance between vertices. The metric induces a natural greedy algorithm for navigating between vertices and we use this to define a pathlength. This pathlength definition, which is implicit in [J. Kleinberg, The small-world phenomenon: an algorithmic perspective, in: Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000] is entirely appropriate in many message passing contexts. Using a Markov chain formulation, we set up a linear system to determine the expected greedy pathlengths and then use techniques from numerical analysis to find a continuum limit. This gives an asymptotically correct expression for the expected greedy pathlength in the limit of large network size: both the leading term and a sharp estimate of the remainder are produced. The results quantify how the greedy pathlength drops as the number of shortcuts is increased. Further, they allow us to measure the amount by which the greedy pathlength, which is based on local information, exceeds the traditional pathlength, which requires knowledge of the whole network. The analysis allows for either O(1) shortcuts per node or O(1) shortcuts per network. In both cases we find that the greedy algorithm fails to exploit fully the existence of short paths