Counting triangles in power-law uniform random graphs

Pu Gao, Remco van der Hofstad, Angus Southwell, Clara Stegehuis

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

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.

Original languageEnglish
Article numberP3.19
Pages (from-to)1-28
Number of pages28
JournalElectronic Journal of Combinatorics
Volume27
Issue number3
DOIs
Publication statusPublished - 7 Aug 2020

Fingerprint Dive into the research topics of 'Counting triangles in power-law uniform random graphs'. Together they form a unique fingerprint.

Cite this