A Lower Bound for Network Navigability

摘要: In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; is, greedy routing computes paths of polylogarithmic expected length between any pairs nodes. This yields the crucial question determining whether such an augmentation is possible for all graphs. this paper, we answer negatively by exhibiting infinite family graphs cannot be augmented navigable whatever distribution edges is. Precisely, it was known doubling dimension at most $O(\log\log n)$ are navigable. We show $\gg\log\log n$, Finally, present a positive navigability result studying special case square arbitrary prove always augmentable latter complements Kleinberg's original and shows adding extra links can sometimes break navigability.