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.
Drawing graphs as nodes connected by links is visually compelling but computationally difficult. Hyperbolic space and spanning trees can reduce visual clutter, speed up layout, and provide fluid interaction. This article briefly describes a software system that explicitly attempts to handle much larger graphs than previous systems and support dynamic exploration rather than final presentation. It then discusses the applicability of this system to goals beyond simple exploration. A software system that supports graph exploration should include both a layout and an interactive drawing component. I have developed new algorithms for both layout and drawing (H3 and H3Viewer). The H3Viewer drawing algorithm remains under development, so this article presents preliminary results. I have implemented a software library that uses these algorithms. It can handle graphs of more than 100,000 edges by using a spanning tree as the backbone for the layout and drawing algorithms. Large-scale data networks form the infrastructure for contemporary global communications. Increasingly, a single network may provide a variety of disparate services, flatter architectures (i.e., fewer controlling hubs) are used to achieve robustness against failure, and networks have to be dynamically and automatically reconfigurable to allow services to be set up quickly. With these trends in mind, it is impractical to perform detailed case-by-case simulations in order to predict and understand the behavior of such large-scale networks. Instead, one has to identify the key structural properties that affect network performance, reliability, and security. These structural properties can then be used to construct models that estimate network behavior in an efficient and scalable manner. A key observation regarding large-scale communications and biological and social networks has been the “small-world” property [1‐3]. More recent network models have focused on power-law degree distributions (PLDD) (for a few examples, see Refs. [4‐6]) as an explanation of or correlated with the small-world property. Evidence for PLDD has been found in data networks at the Internet protocol (IP) layer [7], for the worldwide web [4], and for the virtual network of social connections [8]. Although these features are interesting and important, the impact of intrinsic geometrical and topological features of large-scale networks on performance, reliability, and security is of much greater importance. Intuitively, it is known that traffic between nodes tends to go through a relatively small core of the network, as if the shortest path between them is curved inward. It has been suggested that this property may be due to global curvature or hyperbolicity of the network [9]. Estimating distances in the Internet has been studied in the recent years due to its ability to improve the performance of many applications, e.g., in the peer-to-peer realm. One scalable approach to estimate distances between nodes is to embed the nodes in some d dimensional geometric space and to use the pair distances in this space as the estimate for the real distances. Several algorithms were suggested in the past to do this in low dimensional Euclidean spaces. It was noted in recent years that the Internet structure has a highly connected core and long stretched tendrils, and that most of the routing paths between nodes in the tendrils pass through the core. Therefore, we suggest in this work, to embed the Internet distance metric in a hyperbolic space where routes are bent toward the center. We found that if the curvature, that defines the extend of the bending, is selected in the adequate range, the accuracy of Internet distance embedding can be improved. We demonstrate the strength of our hyperbolic embedding with two applications: selecting the closest server and building an application level multicast tree. For the latter, we present a distributed algorithm for building geometric multicast trees that achieve good trade-offs between delay (stretch) and load (stress). We also present a new efficient centralized embedding algorithm that enables the accurate embedding of short distances, something that have never been done before. The main point of this paper is that network security has a geometric component, in the sense that some architectures promote some aspects of security. Such security issues closely related to the topological architecture of the network graph are multi-path routing to mitigate "eavesdropping" or "packet sniffing", worm propagation and defense, and distributed denial of service (DDoS) attack mitigation. Those geometric aspects relevant to network security are encapsulated in the concept of graph curvature. An architecture that promotes, in some sense, security is the negative curvature of the graph, which is shown to hold in several physical and logical graphs and in the well know "scale free" model. The technique of effective resistance has seen growing popularity in problems ranging from escape probability of random walks on graphs to asymptotic space localization in sensor networks. The results obtained thus far deal with such problems on Euclidean lattices, on which their asymptotic nature already reveals that the crucial issue is the large scale behavior of such lattices. Here we investigate how such results have to be amended on a class of graphs, referred to as Gromov hyperbolic, which behave in the large scale as negatively curved Riemannian manifolds. It is argued that Gromov hyperbolic graphs occur quite naturally in many situations. Among the results developed here, we will mention the nonvanishing probability of escape of a random walk to a Cantor set Gromov boundary and the facts that the space localization error of sensors networked in a Gromov hyperbolic fashion grows linearly with the distance to a sensor whose geographical position is known, but would become uniformly bounded in an idealized situation in which the geographical locations of the nodes at the Gromov boundary are known. In this work we study the asymptotic traffic flow in Gromov's hyperbolic graphs. We prove that under certain mild hypotheses the traffic flow in a hyperbolic graph tends to pass through a finite set of highly congested nodes. These nodes are called the "core" of the graph. We provide a formal definition of the core in a very general context and we study the properties of this set for several graphs. Abstract This paper proposes a mathematical justification of the phenomenon of extreme congestion at a very limited number of nodes in very large networks. It is argued that this phenomenon occurs as a combination of the negative curvature property of the network together with minimum-length routing. More specifically, it is shown that in a large n-dimensional hyperbolic ball B of radius R viewed as a roughly similar model of a Gromov hyperbolic network, the proportion of traffic paths transiting through a small ball near the center is Θ(1), whereas in a Euclidean ball, the same proportion scales as Θ(1 R n−1). This discrepancy persists for the traffic load, which at the center of the hyperbolic ball scales as volume2(B), whereas the same traffic load scales as volume1+1 n (B) in the Euclidean ball. This provides a theoretical justification of the experimental exponent discrepancy observed by Narayan and Saniee between traffic loads in Gromov-hyperbolic networks from the Rocketfuel database and synthetic ...