Critical behavior in inhomogeneous random graphs

Research output: Book/ReportReportAcademic

Abstract

We study the critical behavior of inhomogeneous random graphs where edges are present independently but with unequal edge occupation probabilities. We show that the critical behavior depends sensitively on the properties of the asymptotic degrees. Indeed, when the proportion of vertices with degree at least k is bounded above by k-r+1 for some r > 4, the largest critical connected component is of order n2/3, where n denotes the size of the graph, as on the Erd¿os-R´enyi random graph. The restriction r > 4 corresponds to finite third moment of the degrees. When, the proportion of vertices with degree at least k is asymptotically equal to ck-r+1 for some r ¿ (3, 4), the largest critical connected component is of order n(r-2)/(r-1), instead. Our results show that, for inhomogeneous random graphs with a power-law degree sequence, the critical behavior admits a transition when the third moment of the degrees turns from finite to infinite. Similar phase transitions have been shown to occur for typical distances in such random graphs when the variance of the degrees turns from finite to infinite. We present further results related to the size of the critical or scaling window, and state conjectures for this and related random graph models.
Original languageEnglish
Publishers.n.
Number of pages35
Publication statusPublished - 2009

Publication series

NamearXiv.org [math.PR]
Volume0902.0216

Fingerprint Dive into the research topics of 'Critical behavior in inhomogeneous random graphs'. Together they form a unique fingerprint.

  • Cite this

    Hofstad, van der, R. W. (2009). Critical behavior in inhomogeneous random graphs. (arXiv.org [math.PR]; Vol. 0902.0216). s.n.