TY - JOUR

T1 - Counting triangles in power-law uniform random graphs

AU - Gao, Pu

AU - van der Hofstad, Remco

AU - Southwell, Angus

AU - Stegehuis, Clara

N1 - Funding Information:
? Supported by ARC DE170100716 and ARC DP160100835.? Supported by NWO TOP grant 613.001.451, NWO Gravitation Networks grant 024.002.003 and the NWO VICI grant 639.033.806.? Supported by an Australian Government Research Training Program Scholarship.? Supported by NWO TOP grant 613.001.451.We thank an anonymous referee for pointing out how the integrals in (4.32) and (5.32) could be computed.
Publisher Copyright:
© The authors.

PY - 2020/8/7

Y1 - 2020/8/7

N2 - We count the asymptotic number of triangles in uniform random graphs where the degree distribution follows a power law with degree exponent τ∈(2,3). We also analyze the local clustering coefficient c(k), the probability that two random neighbors of a vertex of degree k are connected. We find that the number of triangles, as well as the local clustering coefficient, scale similarly as in the erased configuration model, where all self-loops and multiple edges of the configuration model are removed. Interestingly, uniform random graphs contain more triangles than erased configuration models with the same degree sequence. The number of triangles in uniform random graphs is closely related to that in a version of the rank-1 inhomogeneous random graph, where all vertices are equipped with weights, and the probabilities that edges are present are moderated by asymptotically linear functions of the products of these vertex weights.

AB - We count the asymptotic number of triangles in uniform random graphs where the degree distribution follows a power law with degree exponent τ∈(2,3). We also analyze the local clustering coefficient c(k), the probability that two random neighbors of a vertex of degree k are connected. We find that the number of triangles, as well as the local clustering coefficient, scale similarly as in the erased configuration model, where all self-loops and multiple edges of the configuration model are removed. Interestingly, uniform random graphs contain more triangles than erased configuration models with the same degree sequence. The number of triangles in uniform random graphs is closely related to that in a version of the rank-1 inhomogeneous random graph, where all vertices are equipped with weights, and the probabilities that edges are present are moderated by asymptotically linear functions of the products of these vertex weights.

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

U2 - 10.37236/9239

DO - 10.37236/9239

M3 - Article

AN - SCOPUS:85090615378

VL - 27

SP - 1

EP - 28

JO - Electronic journal of combinatorics

JF - Electronic journal of combinatorics

SN - 1077-8926

IS - 3

M1 - P3.19

ER -