Optimal subgraph structures in scale-free configuration models

Remco van der Hofstad (Corresponding author), Johan S.H. Van Leeuwaarden (Corresponding author), Clara Stegehuis (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Subgraphs reveal information about the geometry and functionalities of complex networks. For scale-free networks with unbounded degree fluctuations, we obtain the asymptotics of the number of times a small connected graph occurs as a subgraph or as an induced subgraph. We obtain these results by analyzing the configuration model with degree exponent τ ∈ (2, 3) and introducing a novel class of optimization problems. For any given subgraph, the unique optimizer describes the degrees of the vertices that together span the subgraph. We find that subgraphs typically occur between vertices with specific degree ranges. In this way, we can count and characterize all subgraphs. We refrain from double counting in the case of multi-edges, essentially counting the subgraphs in the erased configuration model.

Original languageEnglish
Pages (from-to)501-537
Number of pages37
JournalAnnals of Applied Probability
Volume31
Issue number2
DOIs
Publication statusPublished - Apr 2021

Bibliographical note

Funding Information:
Acknowledgments. The first author was supported by NWO TOP grant 613.001.451 and also supported by NWO Gravitation Networks grant 024.002.003 and NWO VICI grant 639.033.806. The second author was supported by NWO TOP grant 613.001.451 and also supported by NWO Gravitation Networks grant 024.002.003, an NWO TOP-GO grant and an ERC Starting Grant. The third author was supported by NWO TOP grant 613.001.451.

Publisher Copyright:
© Institute of Mathematical Statistics, 2021.

Keywords

  • Configuration model
  • Motifs
  • Random graphs
  • Subgraphs

Fingerprint

Dive into the research topics of 'Optimal subgraph structures in scale-free configuration models'. Together they form a unique fingerprint.

Cite this