Connected Components in Random Graphs Graphs with Given Expected Degree Sequences

Fan Chung and Linyuan Lu

Department of Mathematics, University of California, San Diego, La Jolla,
CA 92093-0112, USA

{fan, llu}@euclid.ucsd.edu

Annals of Combinatorics 6 (2) p.125-145 June, 2002

Abstract:

We consider a family of random graphs with a given expected degree sequence. Each
edge is chosen independently with probability proportional to the product of the
expected degrees of its endpoints. We examine the distribution of the sizes/volumes
of the connected components which turns out depending primarily on the average degree
*d* and the second-order average degree
Here
denotes the weighted average of squares of the expected degrees. For example, we
prove that the giant component exists if the expected average degree *d* is
at least 1, and there is no giant component if the expected second-order average
degree
is at most 1. Examples are given to illustrate that both bounds are best possible.

References:

1. L.A. Adamic and B.A. Huberman, Growth dynamics of the World Wide Web, Nature 401 September 9 (1999) 131.

2. W. Aiello, F. Chung, and L. Lu, A random graph model for massive graphs, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000, pp. 171每180.

3. W. Aiello, F. Chung, and L. Lu, Random evolution in massive graphs, Extended abstract appeared in: The 42th Annual Symposium on Foundation of Computer Sciences, October, 2001, Handbook on Massive Data Sets, Vol. 2, J. Abello, et al., Eds., Kluwer Academic Publishers, 2002, pp. 97每122.

4. L.A.N. Amaral, A. Scala, M. Barth谷l谷my, and H.E. Stanley, Classes of small-world networks, Proc. Natl. Acad. Sci. USA 97 (21) (2000) 11149每11152.

5. N. Alon and J. H. Spencer, The Probabilistic Method, Wiley and Sons, New York, 1992.

6. R.B.R. Azevedo and A.M. Leroi, A power law for cells, Proc. Natl. Acad. Sci. USA 98 (10) (2001) 5699每5704.

7. A.-L. Barab∩asi and R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509每512.

8. A. Barab∩asi, R. Albert, and H. Jeong, Scale-free characteristics of random networks: the topology of the world wide web, Physica A 272 (1999) 173每187.

9. E.A. Bender and E.R. Canfield, The asymptotic number of labelled graphs with given degree sequences, J. Combin. Theory, Ser. A 24 (1978) 296每307.

10. B. Bollob芍s, Random Graphs, Academic, New York, 1985.

11. B. Bollob芍s, O. Riordan, J. Spencer, and G. Tusn芍dy, The degree sequence of a scale-free random graph process, Random Structures Algorithms 18 (3) (2001) 279每290.

12. A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tompkins, and J. Wiener, Graph structure in the web, Proceedings of the WWW9 Conference, May, 2000, Amsterdam, Comput. Networks 33 (1-6) (2000) 309每321.

13. K. Calvert, M. Doar, and E. Zegura, Modeling internet topology, IEEE Commun. Mag. 35 (6) (1997) 160每163.

14. F. Chung and L. Lu, The diameter of random sparse graphs, Adv. Appl. Math. 26 (2001) 257每279.

15. F. Chung and L. Lu, Average distances in random graphs with given expected degree sequences, Proc. Natl. Acad. Sci. USA, to appear.

16. F. Chung, L. Lu, and V. Vu, Eigenvalues of random power law graphs, preprint.

17. C. Cooper and A. Frieze, A general model of web graphs, Proceedings of ESA 2001, pp. 500每511.

18. P. Erdös and T. Gallai, Gráfok elöírt fok迆 pontokkal (Graphs with points of prescribed degrees, in Hungarian), Mat. Lapok 11 (1961) 264每274.

19. P. Erdös and A. R谷nyi, On random graphs, I, Publ. Math. Debrecen 6 (1959) 290每291.

20. M. Faloutsos, P. Faloutsos, and C. Faloutsos, On power-law relationships of the Internet topology, Proceedings SIGCOMM, 1999, pp. 251每262.

21. N. Gilbert, A simulation of the structure of academic science, Socialogical Research Online, 2 (2) 1997.

22. J. Grossman, The Erdös Number Project, http://www.oakland.edu/~grossman/erdoshp.html.

23. S. Jain and S. Krishna, A model for the emergence of cooperation, interdependence, and structure in evolving networks, Proc. Natl. Acad. Sci. USA 98 (2) (2001) 543每547.

24. S. Janson, T. Luczak, and A. Rucinski, Random Graphs, Wiley-Interscience, New York, 2000.

25. J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, The web as a graph: measurements, models and methods, Proceedings of the International Conference on Combinatorics and Computing, 1999, pp. 26每28.

26. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, Trawling the web for emerging cyber communities, Proceedings of the 8th World Wide Web Conference, Toronto, 1999, Extended version in Computer Networks 31 (11每16) (1999) 1481每1493.

27. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, Extracting large-scale knowledge bases from the web, Proceedings of the 25th VLDB Conference, Edinburgh, Scotland, 1999, pp. 639每650.

28. R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal, Stochastic models for the web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000, pp. 57每65.

29. L. Lu, The diameter of random massive graphs, Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 912每921.

30. C. McDiarmid, Concentration, Probabilistic Methods for Algorithmic Discrete Mathematics, Algorithms Combin., 16, Springer, Berlin, 1998, pp. 195每248.

31. M. Molloy and B. Reed, A critical point for random graphs with a given degree sequence, Random Structures Algorithms 6 (2每3) (1995) 161每179.

32. M. Molloy and B. Reed, The size of the giant component of a random graph with a given degree sequence, Combin. Probab. Comput. 7 (3) (1998) 295每305.

33. M.E.J. Newman, The structure of scientific collaboration networks, Proc. Natl. Acad. Sci. USA 98 (2) (2001) 404每409.

34. D. West, Introduction to Graph Theory, Prentice Hall, 1996.

35. N.Wormald, Some problems in the enumeration of labelled graphs, Ph.D. Thesis, Newcastle University, 1978.

36. E. Zegura, K. Calvert, and M. Donahoo, A quantitative comparison of graph-based models for Internet topology, IEEE/ACM Transactions on Networking 5 (6) (1997) 770每783.