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 k=Ω(n) settles on a power law c(k) ∼ n
5
-
2
τ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 the graph size n and eventually for k=Ω(n) settles on a power law c(k) ∼ n
5
-
2
τ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 - 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 -