Navigability is a robust property

DOI10.1007/978-3-319-26784-5_7MaRDI QIDQ3460741zbMATH OpenOpenAlexFDO

Authors Paris Siminelakis, D. Achlioptas

Publication date 8 January 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.04931

zbMATH Keywords

Kleinberg's set systemrank based augmentation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10)

Abstract: 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 to a random destination selected from a carefully crafted probability distribution. Kleinberg proved that RBA makes many networks navigable, i.e., it allows greedy routing to successfully deliver messages between any two vertices in a polylogarithmic number of steps. We prove that navigability is an inherent property of many random networks, arising without coordination, or even independence assumptions.

Recommendations

• A lower bound for network navigability
• Could any graph be turned into a small-world?
• Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation
• Navigable small-world networks with few random bits
• A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability

Cited in

(8)

• Distance-based index structures for fast similarity search
• Navigation in networks by the Bolyai-Lobachevsky hyperbolic geometry
• Symmetric graph properties have independent edges
• Symmetric graph properties have independent edges
• Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation
• Informational cost and networks navigability
• A lower bound for network navigability
• A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability

This page was built for publication: Navigability is a robust property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460741)