On the Hyperbolicity of Small-World Networks and Tree-Like Graphs by Wei Chen, Wenjie Fang, Guangda Hu and Michael W. Mahoney.
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 $\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.
Something to keep you off the streets after work this coming week. 😉
To understand why this work (and work like it is important):
Hyperbolicity, a property of metric spaces that generalizes the idea of Riemannian manifolds with negative curvature, has received considerable attention in both mathematics and computer science. When applied to graphs, as is typical in computer science applications, one may think of hyperbolicity as characterizing a “soft” version of a tree—trees are graphs that have hyperbolicity equal to zero, and graphs that “look like” trees in terms of their metric structure have “small” hyperbolicity. Since trees are an important class of graphs and since tree-like graphs arise in numerous applications, the idea of hyperbolicity has received attention in a range of applications. For example, it has found usefulness in the visualization of the Internet, the Web, and other large graphs []; it has been applied to questions of compact routing, navigation, and decentralized search in Internet graphs and small-world social networks []; and it has been applied to a range of other problems such as distance estimation, network security, sensor networks, and traffic flow and congestion minimization []. (cites omitted)
Interesting question to which I don’t know the answer off hand: Do topic maps exhibit the characteristics of a “small-world network?” Or for that matter, has anyone investigated the nature of the graphs that result from topic maps?
I will be blogging more about the graph nature of topic maps. Please post pointers, suggestions, questions.