Stéphane Boucheron: About the Size of the Giant Component in a Random Graph with Given Degree Distribution

Sparse random graphs with prescribed degree distribution have attracted lot of attention thanks to their relevance to web modeling. Molloy and Reed [MR98] have characterized those limiting degree distributions for which the corresponding random graphs contained with overwhelming probability a giant connected component. We complement their law of large numbers by a central limit theorem: the limiting size of the giant component of random graphs with given degree distribution is Gaussian. The proof revisits the analysis of the fluctuations of the giant component for Erdos-Rényi graphs carried out in Barraez, Boucheron and Fernandez de la Vega [BBFdlV00]. This is a martingale-oriented analysis of a graph exploration.

Bibliography

BBFdlV00
D. Barraez, S. Boucheron, and W. Fernandez de la Vega.
On the fluctuations of the giant component.
Combin. Probab. Comput., 9(4):287-304, 2000.

MR98
Michael Molloy and Bruce Reed.
The size of the giant component of a random graph with a given degree sequence.
Combin. Probab. Comput., 7(3):295-305, 1998.

Back to the Index


Please send comments and corrections to Thomas Klausner.