Scale-free network clustering in hyperbolic and other random graphs

Clara Stegehuis*, Remco van Der Hofstad, Johan S. H. van Leeuwaarden

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Random graphs with power-law degrees can model scale-free networks as sparse topologies with strong degree heterogeneity. Mathematical analysis of such random graphs proved successful in explaining scale-free network properties such as resilience, navigability and small distances. We introduce a variational principle to explain how vertices tend to cluster in triangles as a function of their degrees. We apply the variational principle to the hyperbolic model that quickly gains popularity as a model for scale-free networks with latent geometries and clustering. We show that clustering in the hyperbolic model is non-vanishing and self-averaging, so that a single random graph sample is a good representation in the large-network limit. We also demonstrate the variational principle for some classical random graphs including the preferential attachment model and the configuration model.

Original languageEnglish
Article number295101
JournalJournal of physics a-Mathematical and theoretical
Volume52
Issue number29
DOIs
Publication statusPublished - 19 Jul 2019

Keywords

  • complex networks
  • random graphs
  • hyperbolic model
  • clustering
  • COMPLEX NETWORKS
  • ORGANIZATION
  • DISTANCES
  • WEB
  • DIAMETER
  • INTERNET
  • MODELS

Cite this

@article{f87ad7c49f5c4ca6b2f437046675d4e5,
title = "Scale-free network clustering in hyperbolic and other random graphs",
abstract = "Random graphs with power-law degrees can model scale-free networks as sparse topologies with strong degree heterogeneity. Mathematical analysis of such random graphs proved successful in explaining scale-free network properties such as resilience, navigability and small distances. We introduce a variational principle to explain how vertices tend to cluster in triangles as a function of their degrees. We apply the variational principle to the hyperbolic model that quickly gains popularity as a model for scale-free networks with latent geometries and clustering. We show that clustering in the hyperbolic model is non-vanishing and self-averaging, so that a single random graph sample is a good representation in the large-network limit. We also demonstrate the variational principle for some classical random graphs including the preferential attachment model and the configuration model.",
keywords = "complex networks, random graphs, hyperbolic model, clustering, COMPLEX NETWORKS, ORGANIZATION, DISTANCES, WEB, DIAMETER, INTERNET, MODELS",
author = "Clara Stegehuis and {van Der Hofstad}, Remco and {van Leeuwaarden}, {Johan S. H.}",
year = "2019",
month = "7",
day = "19",
doi = "10.1088/1751-8121/ab2269",
language = "English",
volume = "52",
journal = "Journal of physics a-Mathematical and theoretical",
issn = "1751-8113",
publisher = "IOP Publishing Ltd.",
number = "29",

}

Scale-free network clustering in hyperbolic and other random graphs. / Stegehuis, Clara; van Der Hofstad, Remco; van Leeuwaarden, Johan S. H.

In: Journal of physics a-Mathematical and theoretical, Vol. 52, No. 29, 295101, 19.07.2019.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Scale-free network clustering in hyperbolic and other random graphs

AU - Stegehuis, Clara

AU - van Der Hofstad, Remco

AU - van Leeuwaarden, Johan S. H.

PY - 2019/7/19

Y1 - 2019/7/19

N2 - Random graphs with power-law degrees can model scale-free networks as sparse topologies with strong degree heterogeneity. Mathematical analysis of such random graphs proved successful in explaining scale-free network properties such as resilience, navigability and small distances. We introduce a variational principle to explain how vertices tend to cluster in triangles as a function of their degrees. We apply the variational principle to the hyperbolic model that quickly gains popularity as a model for scale-free networks with latent geometries and clustering. We show that clustering in the hyperbolic model is non-vanishing and self-averaging, so that a single random graph sample is a good representation in the large-network limit. We also demonstrate the variational principle for some classical random graphs including the preferential attachment model and the configuration model.

AB - Random graphs with power-law degrees can model scale-free networks as sparse topologies with strong degree heterogeneity. Mathematical analysis of such random graphs proved successful in explaining scale-free network properties such as resilience, navigability and small distances. We introduce a variational principle to explain how vertices tend to cluster in triangles as a function of their degrees. We apply the variational principle to the hyperbolic model that quickly gains popularity as a model for scale-free networks with latent geometries and clustering. We show that clustering in the hyperbolic model is non-vanishing and self-averaging, so that a single random graph sample is a good representation in the large-network limit. We also demonstrate the variational principle for some classical random graphs including the preferential attachment model and the configuration model.

KW - complex networks

KW - random graphs

KW - hyperbolic model

KW - clustering

KW - COMPLEX NETWORKS

KW - ORGANIZATION

KW - DISTANCES

KW - WEB

KW - DIAMETER

KW - INTERNET

KW - MODELS

U2 - 10.1088/1751-8121/ab2269

DO - 10.1088/1751-8121/ab2269

M3 - Article

VL - 52

JO - Journal of physics a-Mathematical and theoretical

JF - Journal of physics a-Mathematical and theoretical

SN - 1751-8113

IS - 29

M1 - 295101

ER -