Accepted author manuscript, 323 KB, PDF document
Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
The asymptotic variance of the giant component of configuration model random graphs. / Ball, Frank; Neal, Peter John.
In: Annals of Applied Probability, Vol. 27, No. 2, 01.04.2017, p. 1057-1092.Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - The asymptotic variance of the giant component of configuration model random graphs
AU - Ball, Frank
AU - Neal, Peter John
PY - 2017/4/1
Y1 - 2017/4/1
N2 - 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.
AB - 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.
KW - Random graphs
KW - configuration model
KW - branching processes
KW - variance
U2 - 10.1214/16-AAP1225
DO - 10.1214/16-AAP1225
M3 - Journal article
VL - 27
SP - 1057
EP - 1092
JO - Annals of Applied Probability
JF - Annals of Applied Probability
SN - 1050-5164
IS - 2
ER -