Navigable small-world networks with few random bits

DOI10.1016/j.tcs.2009.07.050zbMath1194.68072MaRDI QIDQ1034617

Luisa Gargano, Gennaro Cordasco

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.050

zbMATH Keywords

small-world networks; complex networks; greedy routing; Kleinberg's model

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Degree-optimal routing for P2P systems
• Asymptotically optimal solutions for small world graphs
• Universal augmentation schemes for network navigability
• Could any graph be turned into a small-world?
• Eclecticism shrinks even small worlds
• Close to optimal decentralized routing in long-range contact networks
• The small-world phenomenon
• Know thy neighbor's neighbor
• Low–dimensional lattices. VII. Coordination sequences
• Distance estimation and object location via rings of neighbors
• Evolving Networks with Enhanced Linear Stability Properties
• Collective dynamics of ‘small-world’ networks
• A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability
• How Much Independent Should Individual Contacts Be to Form a Small–World?
• Algorithms – ESA 2005
• Analyzing Kleinberg's (and other) small-world Models