Large deviations for triangles in scale-free random graphs

MaRDI QIDQ6509198arXivFDO

Authors Clara Stegehuis, Bert Zwart

Published in arXiv

Abstract: We provide large deviations estimates for the upper tail of the number of triangles in scale-free inhomogeneous random graphs where the degrees have power law tails with index $-alpha,alphain(1,2)$. We show that upper tail probabilities for triangles undergo a phase transition. For $alpha<4/3$, the upper tail is caused by many vertices of degree of order $n$, and this probability is semi-exponential. In this regime, additional triangles consist of two hubs. For $alpha>4/3$ on the other hand, the upper tail is caused by one hub of a specific degree, and this probability decays polynomially in $n$, leading to additional triangles with one hub. In the intermediate case $alpha=4/3$, we show polynomial decay of the tail probability caused by multiple but finitely many hubs. In this case, the additional triangles contain either a single hub or two hubs. Our proofs are partly based on various concentration inequalities. In particular, we tailor concentration bounds for empirical processes to make them well-suited for analyzing heavy-tailed phenomena in nonlinear settings.

This page was built for publication: Large deviations for triangles in scale-free random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509198)