Clustering Implies Geometry in Networks

D. Krioukov
Physical Review Letters
v.116, 208302, 2016
May 19, 2016

Abstract

Network models with  latent geometry have been used successfully in many applications in network  science and other disciplines, yet it is usually impossible to tell if a  given real network is geometric, meaning if it is a typical element in an  ensemble of random geometric graphs. Here we identify structural properties  of networks that guarantee that random graphs having these properties are  geometric. Specifically we show that random graphs in which expected degree  and clustering of every node are fixed to some constants are equivalent to  random geometric graphs on the real line, if clustering is sufficiently  strong. Large numbers of triangles, homogeneously distributed across all  nodes as in real networks, are thus a consequence of network geometricity.  The methods we use to prove this are quite general and applicable to other  network ensembles, geometric or not, and to certain problems in quantum  gravity.

Related publications