Paper Info
Title
On the Hyperbolicity of Small-World and Tree-Like Random Graphs.
Abstract
Hyperbolicity is a property of a graph that may be viewed as being a "soft" version of a tree, and recent empirical and theoretical work has suggested that many graphs arising in Internet and related data applications have hyperbolic properties. Here, we consider Gromov's notion of d-hyperbolicity, and we establish several positive and negative results for small-world and tree-like random graph models. In particular, we show that small-world random graphs built from underlying grid structures do not have strong improvement in hyperbolicity, even when the rewiring greatly improves decentralized navigation. On the other hand, for a class of tree-like graphs called ringed trees that have constant hyperbolicity, adding random links among the leaves in a manner similar to the small-world graph constructions may easily destroy the hyperbolicity of the graphs, except for a class of random edges added using an exponentially decaying probability function based on the ring distance among the leaves. Our study provides the first significant analytical results on the hyperbolicity of a rich class of random graphs, which shed light on the relationship between hyperbolicity and navigability of random graphs, as well as on the sensitivity of hyperbolic delta to noises in random graphs.
Year
DOI
Venue
2012
null
ALGORITHMS AND COMPUTATION, ISAAC 2012
Keywords
Field
DocType
Graph hyperbolicity,complex networks,small-world networks,random graphs,decentralized navigation
Discrete mathematics,Random regular graph,Modular decomposition,Combinatorics,Indifference graph,Random graph,Lévy family of graphs,Chordal graph,Distance,Pathwidth,Mathematics
Conference
Volume
Issue
ISSN
7676
null
0302-9743
Citations 
PageRank 
References 
17
0.75
24
Authors
4
Name
Order
Citations
PageRank
Wei Chen13416170.71
Wenjie Fang2287.68
Guang-da Hu313318.39
Michael W. Mahoney43297218.10