Clustering Implies Geometry in Networks

Dmitri Krioukov
Phys. Rev. Lett. 116, 208302 – Published 19 May 2016
PDFHTMLExport Citation

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.

  • Figure
  • Figure
  • Received 2 April 2016

DOI:https://doi.org/10.1103/PhysRevLett.116.208302

© 2016 American Physical Society

Physics Subject Headings (PhySH)

Networks

Authors & Affiliations

Dmitri Krioukov

  • Northeastern University, Departments of Physics, Mathematics, and Electrical and Computer Engineering, Boston, Massachusetts 02115, USA

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 116, Iss. 20 — 20 May 2016

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×