Critical behavior in inhomogeneous random graphs

Onderzoeksoutput: Boek/rapportRapportAcademic

Samenvatting

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.
Originele taal-2Engels
Uitgeverijs.n.
Aantal pagina's35
StatusGepubliceerd - 2009

Publicatie series

NaamarXiv.org [math.PR]
Volume0902.0216

Vingerafdruk Duik in de onderzoeksthema's van 'Critical behavior in inhomogeneous random graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit