Could any graph be turned into a small-world?

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

Emmanuelle Lebhar, Nicolas Hanusse, Philippe Duchon, 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 algorithmRandom graph modelSmall-world

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Could any graph be turned into a small-world?