Triadic closure in configuration models with unbounded degree fluctuations

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
26 Downloads (Pure)

Abstract

The configuration model generates random graphs with any given degree distribution, and thus serves as a null model for scale-free networks with power-law degrees and unbounded degree fluctuations. For this setting, we study the local clustering c(k), i.e., the probability that two neighbors of a degree-k node are neighbors themselves. We show that c(k) progressively falls off with k and the graph size n and eventually for (Formula presented.) settles on a power law (Formula presented.) with (Formula presented.) the power-law exponent of the degree distribution. This fall-off has been observed in the majority of real-world networks and signals the presence of modular or hierarchical structure. Our results agree with recent results for the hidden-variable model and also give the expected number of triangles in the configuration model when counting triangles only once despite the presence of multi-edges. We show that only triangles consisting of triplets with uniquely specified degrees contribute to the triangle counting.

Original languageEnglish
Pages (from-to)746-774
Number of pages29
JournalJournal of Statistical Physics
Volume173
Issue number3-4
DOIs
Publication statusPublished - 1 Nov 2018

Fingerprint

triangles
closures
Triangle
Closure
Fluctuations
Power Law
Configuration
Degree Distribution
configurations
Counting
counting
Hidden Variables
Scale-free Networks
Hierarchical Structure
Random Graphs
Model
Null
Exponent
Clustering
exponents

Keywords

  • Clustering
  • Configuration model
  • Random graphs

Cite this

@article{bedf9fe17c174e4eb02ac47fced30fee,
title = "Triadic closure in configuration models with unbounded degree fluctuations",
abstract = "The configuration model generates random graphs with any given degree distribution, and thus serves as a null model for scale-free networks with power-law degrees and unbounded degree fluctuations. For this setting, we study the local clustering c(k), i.e., the probability that two neighbors of a degree-k node are neighbors themselves. We show that c(k) progressively falls off with k and the graph size n and eventually for (Formula presented.) settles on a power law (Formula presented.) with (Formula presented.) the power-law exponent of the degree distribution. This fall-off has been observed in the majority of real-world networks and signals the presence of modular or hierarchical structure. Our results agree with recent results for the hidden-variable model and also give the expected number of triangles in the configuration model when counting triangles only once despite the presence of multi-edges. We show that only triangles consisting of triplets with uniquely specified degrees contribute to the triangle counting.",
keywords = "Clustering, Configuration model, Random graphs",
author = "{van der Hofstad}, Remco and {van Leeuwaarden}, {Johan S.H.} and Clara Stegehuis",
year = "2018",
month = "11",
day = "1",
doi = "10.1007/s10955-018-1952-x",
language = "English",
volume = "173",
pages = "746--774",
journal = "Journal of Statistical Physics",
issn = "0022-4715",
publisher = "Springer",
number = "3-4",

}

Triadic closure in configuration models with unbounded degree fluctuations. / van der Hofstad, Remco; van Leeuwaarden, Johan S.H.; Stegehuis, Clara.

In: Journal of Statistical Physics, Vol. 173, No. 3-4, 01.11.2018, p. 746-774.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Triadic closure in configuration models with unbounded degree fluctuations

AU - van der Hofstad, Remco

AU - van Leeuwaarden, Johan S.H.

AU - Stegehuis, Clara

PY - 2018/11/1

Y1 - 2018/11/1

N2 - The configuration model generates random graphs with any given degree distribution, and thus serves as a null model for scale-free networks with power-law degrees and unbounded degree fluctuations. For this setting, we study the local clustering c(k), i.e., the probability that two neighbors of a degree-k node are neighbors themselves. We show that c(k) progressively falls off with k and the graph size n and eventually for (Formula presented.) settles on a power law (Formula presented.) with (Formula presented.) the power-law exponent of the degree distribution. This fall-off has been observed in the majority of real-world networks and signals the presence of modular or hierarchical structure. Our results agree with recent results for the hidden-variable model and also give the expected number of triangles in the configuration model when counting triangles only once despite the presence of multi-edges. We show that only triangles consisting of triplets with uniquely specified degrees contribute to the triangle counting.

AB - The configuration model generates random graphs with any given degree distribution, and thus serves as a null model for scale-free networks with power-law degrees and unbounded degree fluctuations. For this setting, we study the local clustering c(k), i.e., the probability that two neighbors of a degree-k node are neighbors themselves. We show that c(k) progressively falls off with k and the graph size n and eventually for (Formula presented.) settles on a power law (Formula presented.) with (Formula presented.) the power-law exponent of the degree distribution. This fall-off has been observed in the majority of real-world networks and signals the presence of modular or hierarchical structure. Our results agree with recent results for the hidden-variable model and also give the expected number of triangles in the configuration model when counting triangles only once despite the presence of multi-edges. We show that only triangles consisting of triplets with uniquely specified degrees contribute to the triangle counting.

KW - Clustering

KW - Configuration model

KW - Random graphs

UR - http://www.scopus.com/inward/record.url?scp=85040906975&partnerID=8YFLogxK

U2 - 10.1007/s10955-018-1952-x

DO - 10.1007/s10955-018-1952-x

M3 - Article

C2 - 30930481

AN - SCOPUS:85040906975

VL - 173

SP - 746

EP - 774

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

SN - 0022-4715

IS - 3-4

ER -