Open Collections

Clustering Implies Geometry in Networks

Banff International Research Station for Mathematical Innovation and Discovery

Two common features of many large real networks are that they are sparse and that they have strong clustering, i.e., large number of triangles homogeneously distributed across all nodes. In many growing real networks for which historical data is available, the average degree and clus- tering are roughly independent of the growing network size. Recently, (soft) random geometric graphs, also known as latent-space network models, with hyperbolic and de Sitter latent geome- tries have been used successfully to model these features of real networks, to predict missing and future links in them, and to study their navigability, with applications ranging from designing optimal routing in the Internet, to identification of the information-transmission skeleton in the human brain. Yet it remains unclear if latent-space models are indeed adequate models of real networks, as random graphs in these models may have structural properties that real networks do not have, or vice versa. We show that the canonical maximum-entropy ensemble of random graphs in which the expected numbers of edges and triangles at every node are fixed to constants, are approximately soft random geometric graphs on the real line. The approximation is exact in the limit of standard random geometric graphs with a sharp connectivity threshold and strongest clustering. This result implies that a large number of triangles homogeneously distributed across all vertices is not only necessary but also a sufficient condition for the presence of a latent/effective metric space in large sparse networks. Strong clustering, ubiquitously observed in real networks, is thus a reflection of their latent geometry.

Mathematics; Combinatorics; Probability theory and stochastic processes

video/mp4

Author affiliation: Northeastern University

2017-05-10

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/61566

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/