Triadic closure in configuration models with unbounded degree fluctuations

Research output: Contribution to journalArticleAcademic

49 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 eventually for k=Ω(n − − √ ) settles on a power law c(k)∼k −2(3−τ) with τ∈(2,3) 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
Article number1710.02027v1
Number of pages25
JournalarXiv
Issue number1710.02027
Publication statusPublished - 5 Oct 2017

Fingerprint

triangles
closures
configurations
counting
exponents

Cite this

@article{e5774f73c93f4e2cb96c10df90c98aae,
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 eventually for k=Ω(n − − √ ) settles on a power law c(k)∼k −2(3−τ) with τ∈(2,3) 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 = "math.PR",
author = "{van der Hofstad}, R.W. and {van Leeuwaarden}, J.S.H. and C. Stegehuis",
year = "2017",
month = "10",
day = "5",
language = "English",
journal = "arXiv",
publisher = "Cornell University Library",
number = "1710.02027",

}

Triadic closure in configuration models with unbounded degree fluctuations. / van der Hofstad, R.W.; van Leeuwaarden, J.S.H.; Stegehuis, C.

In: arXiv, No. 1710.02027, 1710.02027v1, 05.10.2017.

Research output: Contribution to journalArticleAcademic

TY - JOUR

T1 - Triadic closure in configuration models with unbounded degree fluctuations

AU - van der Hofstad, R.W.

AU - van Leeuwaarden, J.S.H.

AU - Stegehuis, C.

PY - 2017/10/5

Y1 - 2017/10/5

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 eventually for k=Ω(n − − √ ) settles on a power law c(k)∼k −2(3−τ) with τ∈(2,3) 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 eventually for k=Ω(n − − √ ) settles on a power law c(k)∼k −2(3−τ) with τ∈(2,3) 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 - math.PR

M3 - Article

JO - arXiv

JF - arXiv

IS - 1710.02027

M1 - 1710.02027v1

ER -