On the Hyperbolicity of Small-World Networks and Tree-Like Graphs

Details On the Hyperbolicity of Small-World Networks and Tree-Like Graphs On the Hyperbolicity of Small-World Networks and Tree-Like Graphs

2012-01-09

arxiv.org/abs/1201.1717v1

Computer Science

Social and Information Networks

38 pages, 1 figure

Scientific paper

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 $\delta$-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. In addition to being of interest in their own right, our main results shed light on the relationship between hyperbolicity and navigability, as well as the relationship between $\delta$-hyperbolicity and the use of randomness in common random graph constructions.

Affiliated with

Also associated with

No associations

Rating

On the Hyperbolicity of Small-World Networks and Tree-Like Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Hyperbolicity of Small-World Networks and Tree-Like Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Hyperbolicity of Small-World Networks and Tree-Like Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-643091