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. We consider Gromov's notion of -hyperbolicity, and establish several results for small-world and tree-like random graph models. First, we study the hyperbolicity of Kleinberg small-world random graphs and show that the hyperbolicity of these random graphs is not significantly improved comparing to graph diameter even when it greatly improves decentralized navigation. Next we study a class of tree-like graphs called ringed trees that have constant hyperbolicity. We show that adding random links among the leaves 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 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 to noises in random graphs.
Another approach taken by several recent papers is to build random graphs from hyperbolic metric spaces and then shows that such random graphs lead to several common properties of small-world complex networks, including good navigability properties @cite_6 @cite_19 @cite_31 @cite_42 . While assuming a low hyperbolicity metric space to build random graphs in these studies makes intuitive sense, it is difficult to prove nontrivial results on the Gromov's @math of these random graphs even for simple random graph models that are intuitively tree-like.
@cite_19 @cite_31 @cite_42 @cite_6
2104099158 2128738155 2028203362 2141663929
We consider the Erdős–Renyi random graph G(n, p) inside the critical window, that is when p = 1 n + λn −4 3, for some fixed ( R ) . We prove that the sequence of connected components of G(n, p), considered as metric spaces using the graph distance rescaled by n −1 3, converges towards a sequence of continuous compact metric spaces. The result relies on a bijection between graphs and certain marked random walks, and the theory of continuum random trees. Our result gives access to the answers to a great many questions about distances in critical random graphs. In particular, we deduce that the diameter of G(n, p) rescaled by n −1 3 converges in distribution to an absolutely continuous random variable with finite mean. We look at a model of random graphs suggested by Gilbert: given an integer @math and @math , scatter @math vertices independently and uniformly on a metric space, and then add edges connecting pairs of vertices of distance less than @math apart.We consider the asymptotics when the metric space is the interval [0, 1], and @math is a function of @math , for @math . We prove that every upwards closed property of (ordered) graphs has at least a weak threshold in this model on this metric space. (But we do find a metric space on which some upwards closed properties do not even have weak thresholds in this model.) We also prove that every upwards closed property with a threshold much above connectivity's threshold has a strong threshold. (But we also find a sequence of upwards closed properties with lower thresholds that are strictly weak.) We consider monotone embeddings of a finite metric space into low-dimensional normed space. That is, embeddings that respect the order among the distances in the original space. Our main interest is in embeddings into Euclidean spaces. We observe that any metric on n points can be embedded into l2n, while (in a sense to be made precise later), for almost every n-point metric space, every monotone map must be into a space of dimension Ω(n) (Lemma 3).It becomes natural, then, to seek explicit constructions of metric spaces that cannot be monotonically embedded into spaces of sublinear dimension. To this end, we employ known results on sphericity of graphs, which suggest one example of such a metric space--that is defined by a complete bipartite graph. We prove that an δn-regular graph of order n, with bounded diameter has sphericity Ω(n (λ2+1)), where λ2 is the second largest eigenvalue of the adjacency matrix of the graph, and 0<δ≤½ is constant (Theorem 4). We also show that while random graphs have linear sphericity, there are quais-random graphs of logarithmic sphericity (Lemma 7).For the above bound to be linear, λ2 must be constant. We show that if the second eigenvalue of an n 2-regular graph is bounded by a constant, then the graph is close to being complete bipartite. Namely, its adjacency matrix differs from that of a complete bipartite graph in only o(n2) entries (Theorem 5). Furthermore, for any 0<δ<½, and λ2, there are only finitely many δn-regular graphs with second eigenvalue at most λ2 (Corollary 4). δ-Hyperbolic metric spaces have been defined by M. Gromov in 1987 via a simple 4-point condition: for any four points u,v,w,x, the two larger of the distance sums d(u,v)+d(w,x),d(u,w)+d(v,x),d(u,x)+d(v,w) differ by at most 2δ. They play an important role in geometric group theory, geometry of negatively curved spaces, and have recently become of interest in several domains of computer science, including algorithms and networking. In this paper, we study unweighted δ-hyperbolic graphs. Using the Layering Partition technique, we show that every n-vertex δ-hyperbolic graph with δ≥1 2 has an additive O(δlog n)-spanner with at most O(δn) edges and provide a simpler, in our opinion, and faster construction of distance approximating trees of δ-hyperbolic graphs with an additive error O(δlog n). The construction of our tree takes only linear time in the size of the input graph. As a consequence, we show that the family of n-vertex δ-hyperbolic graphs with δ≥1 2 admits a routing labeling scheme with O(δlog 2 n) bit labels, O(δlog n) additive stretch and O(log 2(4δ)) time routing protocol, and a distance labeling scheme with O(log 2 n) bit labels, O(δlog n) additive error and constant time distance decoder.