Navigability is a Robust Property

摘要: The Small World phenomenon has inspired researchers across a number of fields. A breakthrough in its understanding was made by Kleinberg who introduced Rank Based Augmentation RBA: add to each vertex independently an arc random destination, selected from carefully crafted probability distribution. proved that RBA makes many networks navigable, i.e., it allows greedy routing successfully deliver messages between any two vertices polylogarithmic steps. Our goal this work is prove navigability inherent, robust property networks, requiring no augmentation, coordination, or even independence assumptions. framework assigns cost edge and considers the uniform measure over all graphs on n satisfy total budget constraint. We show when function sufficiently correlated with underlying geometry for wide range budgets, overwhelming majority feasible given are navigable. provide new set geometric conditions generalize Kleinberg's systems as well unified analysis navigability.