The phase transition in inhomogeneous random graphs
We introduce a very general model of an inhomogenous random graph with 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 pro...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2005
|
| _version_ | 1826281781580529664 |
|---|---|
| author | Bollobas, B Janson, S Riordan, O |
| author_facet | Bollobas, B Janson, S Riordan, O |
| author_sort | Bollobas, B |
| collection | OXFORD |
| description | We introduce a very general model of an inhomogenous random graph with 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). |
| first_indexed | 2024-03-07T00:33:58Z |
| format | Journal article |
| id | oxford-uuid:80c1c080-8a51-47ff-88e2-f697d7d89f13 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:33:58Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | oxford-uuid:80c1c080-8a51-47ff-88e2-f697d7d89f132022-03-26T21:25:35ZThe phase transition in inhomogeneous random graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:80c1c080-8a51-47ff-88e2-f697d7d89f13EnglishSymplectic Elements at Oxford2005Bollobas, BJanson, SRiordan, OWe introduce a very general model of an inhomogenous random graph with 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). |
| spellingShingle | Bollobas, B Janson, S Riordan, O The phase transition in inhomogeneous random graphs |
| title | The phase transition in inhomogeneous random graphs |
| title_full | The phase transition in inhomogeneous random graphs |
| title_fullStr | The phase transition in inhomogeneous random graphs |
| title_full_unstemmed | The phase transition in inhomogeneous random graphs |
| title_short | The phase transition in inhomogeneous random graphs |
| title_sort | phase transition in inhomogeneous random graphs |
| work_keys_str_mv | AT bollobasb thephasetransitionininhomogeneousrandomgraphs AT jansons thephasetransitionininhomogeneousrandomgraphs AT riordano thephasetransitionininhomogeneousrandomgraphs AT bollobasb phasetransitionininhomogeneousrandomgraphs AT jansons phasetransitionininhomogeneousrandomgraphs AT riordano phasetransitionininhomogeneousrandomgraphs |