The small giant component in scale-free random graphs
Building on the methods developed in joint work with Béla Bollobás and Svante Janson, we study the phase transition in four 'scale-free' random graph models, obtaining upper and lower bounds on the size of the giant component when there is one. In particular, we determine the extremely slo...
| Автор: | |
|---|---|
| Формат: | Journal article |
| Мова: | English |
| Опубліковано: |
2005
|
| _version_ | 1826281254084935680 |
|---|---|
| author | Riordan, O |
| author_facet | Riordan, O |
| author_sort | Riordan, O |
| collection | OXFORD |
| description | Building on the methods developed in joint work with Béla Bollobás and Svante Janson, we study the phase transition in four 'scale-free' random graph models, obtaining upper and lower bounds on the size of the giant component when there is one. In particular, we determine the extremely slow rate of growth of the giant component just above the phase transition. We greatly reduce the significant gaps between the existing upper and lower bounds, giving bounds that match to within a factor $1+o(1)$ in the exponent. In all cases the method used is to couple the neighbourhood expansion process in the graph on n vertices with a continuous-type branching process that is independent of n. It can be shown (requiring some separate argument for each case) that with probability tending to 1 as $n\to\infty$ the size of the giant component divided by n is within $o(1)$ of the survival probability $\ sigma$ of the branching process. This survival probability is given in terms of the maximal solution $\phi$ to certain non-linear integral equations, which can be written in the form φ=F(φ) for a certain operator F. Upper and lower bounds are found by constructing trial functions $\phi_0$, $\phi_1$ with F(φ0)≤ φ0 and $F(φ1)≥ φ1 holding pointwise; basic properties of branching processes then imply that $\phi_1\leq \phi\leq \phi_0$, giving upper and lower bounds on $\sigma$. © 2005 Cambridge University Press. |
| first_indexed | 2024-03-07T00:26:02Z |
| format | Journal article |
| id | oxford-uuid:7e296b0d-d1fd-4de1-b2df-1c2ecb3903d2 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:26:02Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | oxford-uuid:7e296b0d-d1fd-4de1-b2df-1c2ecb3903d22022-03-26T21:08:30ZThe small giant component in scale-free random graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7e296b0d-d1fd-4de1-b2df-1c2ecb3903d2EnglishSymplectic Elements at Oxford2005Riordan, OBuilding on the methods developed in joint work with Béla Bollobás and Svante Janson, we study the phase transition in four 'scale-free' random graph models, obtaining upper and lower bounds on the size of the giant component when there is one. In particular, we determine the extremely slow rate of growth of the giant component just above the phase transition. We greatly reduce the significant gaps between the existing upper and lower bounds, giving bounds that match to within a factor $1+o(1)$ in the exponent. In all cases the method used is to couple the neighbourhood expansion process in the graph on n vertices with a continuous-type branching process that is independent of n. It can be shown (requiring some separate argument for each case) that with probability tending to 1 as $n\to\infty$ the size of the giant component divided by n is within $o(1)$ of the survival probability $\ sigma$ of the branching process. This survival probability is given in terms of the maximal solution $\phi$ to certain non-linear integral equations, which can be written in the form φ=F(φ) for a certain operator F. Upper and lower bounds are found by constructing trial functions $\phi_0$, $\phi_1$ with F(φ0)≤ φ0 and $F(φ1)≥ φ1 holding pointwise; basic properties of branching processes then imply that $\phi_1\leq \phi\leq \phi_0$, giving upper and lower bounds on $\sigma$. © 2005 Cambridge University Press. |
| spellingShingle | Riordan, O The small giant component in scale-free random graphs |
| title | The small giant component in scale-free random graphs |
| title_full | The small giant component in scale-free random graphs |
| title_fullStr | The small giant component in scale-free random graphs |
| title_full_unstemmed | The small giant component in scale-free random graphs |
| title_short | The small giant component in scale-free random graphs |
| title_sort | small giant component in scale free random graphs |
| work_keys_str_mv | AT riordano thesmallgiantcomponentinscalefreerandomgraphs AT riordano smallgiantcomponentinscalefreerandomgraphs |