The asymptotic variance of the giant component of configuration model random graphs
For a supercritical configuration model random graph it is well known that, subject to mild conditions, there exists a unique giant component, whose size $R_n$ is $O (n)$, where $n$ is the total number of vertices in the random graph. Moreover, there exists $0 < \rho \leq 1$ such that $R_n/n \con...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Published: |
Institute of Mathematical Statistics
2017
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/34282/ |
| _version_ | 1848794815934758912 |
|---|---|
| author | Ball, Frank Neal, Peter |
| author_facet | Ball, Frank Neal, Peter |
| author_sort | Ball, Frank |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | For a supercritical configuration model random graph it is well known that, subject to mild conditions, there exists a unique giant component, whose size $R_n$ is $O (n)$, where $n$ is the total number of vertices in the random graph. Moreover, there exists $0 < \rho \leq 1$ such that $R_n/n \convp \rho$ as $\nr$. We show that for a sequence of {\it well-behaved} configuration model random graphs with a deterministic degree sequence satisfying $0 < \rho < 1$, there exists $\sigma^2 > 0$, such that $var (\sqrt{n} (R_n/n -\rho)) \rightarrow \sigma^2$ as $\nr$. Moreover, an explicit, easy to compute, formula is given for $\sigma^2$. This provides a key stepping stone for computing the asymptotic variance of the size of the giant component for more general random graphs. |
| first_indexed | 2025-11-14T19:22:12Z |
| format | Article |
| id | nottingham-34282 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:22:12Z |
| publishDate | 2017 |
| publisher | Institute of Mathematical Statistics |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-342822020-05-04T18:46:55Z https://eprints.nottingham.ac.uk/34282/ The asymptotic variance of the giant component of configuration model random graphs Ball, Frank Neal, Peter For a supercritical configuration model random graph it is well known that, subject to mild conditions, there exists a unique giant component, whose size $R_n$ is $O (n)$, where $n$ is the total number of vertices in the random graph. Moreover, there exists $0 < \rho \leq 1$ such that $R_n/n \convp \rho$ as $\nr$. We show that for a sequence of {\it well-behaved} configuration model random graphs with a deterministic degree sequence satisfying $0 < \rho < 1$, there exists $\sigma^2 > 0$, such that $var (\sqrt{n} (R_n/n -\rho)) \rightarrow \sigma^2$ as $\nr$. Moreover, an explicit, easy to compute, formula is given for $\sigma^2$. This provides a key stepping stone for computing the asymptotic variance of the size of the giant component for more general random graphs. Institute of Mathematical Statistics 2017-05-26 Article PeerReviewed Ball, Frank and Neal, Peter (2017) The asymptotic variance of the giant component of configuration model random graphs. Annals of Applied Probability, 27 (2). pp. 1057-1092. ISSN 1050-5164 Random graphs configuration model branching processes variance http://projecteuclid.org/euclid.aoap/1495764374 doi:10.1214/16-AAP1225 doi:10.1214/16-AAP1225 |
| spellingShingle | Random graphs configuration model branching processes variance Ball, Frank Neal, Peter The asymptotic variance of the giant component of configuration model random graphs |
| title | The asymptotic variance of the giant component of configuration model random graphs |
| title_full | The asymptotic variance of the giant component of configuration model random graphs |
| title_fullStr | The asymptotic variance of the giant component of configuration model random graphs |
| title_full_unstemmed | The asymptotic variance of the giant component of configuration model random graphs |
| title_short | The asymptotic variance of the giant component of configuration model random graphs |
| title_sort | asymptotic variance of the giant component of configuration model random graphs |
| topic | Random graphs configuration model branching processes variance |
| url | https://eprints.nottingham.ac.uk/34282/ https://eprints.nottingham.ac.uk/34282/ https://eprints.nottingham.ac.uk/34282/ |