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.
|Number of pages||35|
|Publication status||Published - 2009|