uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
The phase transition in inhomogeneous random graphs
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2007 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 31, no 1, 3-122 p.Article in journal (Refereed) Published
Abstract [en]

The "classical" random graph models, in particular G(n,p), are "homogeneous," in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power-law degree distributions. Thus there has been a lot of recent interest in defining and studying "inhomogeneous" random graph models.

One of the most studied properties of these new models is their "robustness", or, equivalently, the "phase transition" as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years.

Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence.

Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n, p) used to study the phase transition; also, it seems to be a property of many large real-world graphs. Our model includes as special cases many models previously studied.

We show that, under one very weak assumption (that the expected number of edges is "what it should be"), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze.

We also consider other properties of the model, showing, for example, that when there is a giant component, it is "stable": for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n).

Place, publisher, year, edition, pages
2007. Vol. 31, no 1, 3-122 p.
Keyword [en]
sparse inhomogeneous random graphs, branching process, phase transition
National Category
URN: urn:nbn:se:uu:diva-26311DOI: 10.1002/rsa.20168ISI: 000248254500002OAI: oai:DiVA.org:uu-26311DiVA: diva2:54085
Available from: 2007-02-15 Created: 2007-02-15 Last updated: 2011-02-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Janson, Svante
By organisation
Department of Mathematics
In the same journal
Random structures & algorithms (Print)

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 182 hits
ReferencesLink to record
Permanent link

Direct link