Could any graph be turned into a small-world?

DOI10.1016/j.tcs.2005.12.008zbMath1088.68141MaRDI QIDQ2368969

Nicolas Hanusse, Philippe Duchon, Emmanuelle Lebhar, Nicolas Schabanel

Publication date: 28 April 2006

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

Full work available at URL: https://hal-lara.archives-ouvertes.fr/hal-02101877/file/RR2004-61.pdf

zbMATH Keywords

Routing algorithm; Random graph model; Small-world

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

Related Items

Low-Distortion Inference of Latent Similarities from a Multiplex Social Network, Depth of Field and Cautious-Greedy Routing in Social Networks, Delay of Social Search on Small-World Graphs, Category-based routing in social networks: membership dimension and the small-world phenomenon, Neighbor selection and hitting probability in small-world graphs, Recovering the long-range links in augmented graphs, Universal augmentation schemes for network navigability, Navigable small-world networks with few random bits, Distance estimation and object location via rings of neighbors, Greedy routing in small-world networks with power-law degrees

Cites Work

• Renormalization group analysis of the small-world network model
• The diameter of a long-range percolation graph
• The small-world phenomenon
• Know thy neighbor's neighbor
• Collective dynamics of ‘small-world’ networks
• Automata, Languages and Programming
• Eclecticism shrinks even small worlds
• Analyzing Kleinberg's (and other) small-world Models
• Unnamed Item
• Unnamed Item
• Unnamed Item