Hyperbolicity is a property of a graph that may be viewed as 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 δ-hyperbolicity and establish several positive and negative results for small-world and treelike random graph models. First, we study the hyperbolicity of the class of Kleinberg small-world random graphs , where _n_ is the number of vertices in the graph, _d_ is the dimension of the underlying base grid _B_, and γ is the small-world parameter such that each node _u_ in the graph connects to another node _v_ in the graph with probability proportional to 1/_d_B_(_u_, _v_)^γ, with _d_B_(_u_, _v_) the grid distance from _u_ to _v_ in the base grid _B_. We show that when γ=_d_, the parameter value allowing efficient decentralized routing in Kleinberg's small-world network,the hyperbolic δ is with probability 1−_o_(1) for every ϵ>0 independent of _n_. We see that hyperbolicity is not significantly improved in relation to graph diameter even when the long-range connections greatly improve decentralized navigation. We also show that for other values of γ, the hyperbolic δ is very close to the graph diameter, indicating poor hyperbolicity in these graphs as well. Next we study a class of treelike graphs called ringed trees that have constant hyperbolicity. We show that 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 one of the first significant analytic results on the hyperbolicity of a rich class of random graphs, which sheds light on the relationship between hyperbolicity and navigability of random graphs, as well as on the sensitivity of hyperbolic δ to noises in random graphs.

On the Hyperbolicity of Small-World and Treelike Random Graphs