Navigability is a robust property

DOI10.1007/978-3-319-26784-5_7zbMATH Open1342.05150arXiv1501.04931OpenAlexW1489581814MaRDI QIDQ3460741FDOQ3460741

Authors: Paris Siminelakis, D. Achlioptas 

Publication date: 8 January 2016

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

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.

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

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

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)

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)