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 language | English |
|---|---|
| Pages (from-to) | 746-774 |
| Number of pages | 29 |
| Journal | Journal of Statistical Physics |
| Volume | 173 |
| Issue number | 3-4 |
| DOIs | |
| Publication status | Published - 1 Nov 2018 |
Fingerprint
Keywords
- Clustering
- Configuration model
- Random graphs
Cite this
}
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 journal › Article › Academic › peer-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 -