Recovering the long-range links in augmented graphs

DOI10.1016/j.tcs.2010.01.009zbMath1195.68014OpenAlexW2002330840MaRDI QIDQ962166

Emmanuelle Lebhar, Zvi Lotker, Pierre Fraigniaud

Publication date: 6 April 2010

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

Full work available at URL: https://hal.inria.fr/inria-00147536/file/RRversion1.pdf

zbMATH Keywords

doubling dimensionbounded growthsmall world

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Navigation in spatial networks: a survey ⋮ Low-Distortion Inference of Latent Similarities from a Multiplex Social Network

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Universal augmentation schemes for network navigability
• Lectures on analysis on metric spaces
• Could any graph be turned into a small-world?
• Emergence of Scaling in Random Networks
• The small-world phenomenon
• Finding nearest neighbors in growth-restricted metrics
• Know thy neighbor's neighbor
• The Structure and Function of Complex Networks
• Fault-tolerant routing in peer-to-peer systems
• Distance estimation and object location via rings of neighbors
• Object location using path separators
• Collective dynamics of ‘small-world’ networks
• Distributed Computing
• A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability
• Navigating Low-Dimensional and Hierarchical Population Networks
• Automata, Languages and Programming
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Modeling the Small-World Phenomenon with Local Network Flow
• Algorithms – ESA 2005
• Eclecticism shrinks even small worlds
• Analyzing Kleinberg's (and other) small-world Models
• On the bias of traceroute sampling