Convergence law for random graphs with specified degree sequence

ABSTRACT

The degree sequence of an n-vertex graph is d0,…,dn−1, where each di is the number of vertices of degree i in the graph. A random graph with degree sequence d0,…,dn−1 is a randomly selected member of the set of graphs on {1,…,n} with that degree sequence, all choices being equally likely. Let λ0,λ1,… be a sequence of nonnegative reals summing to 1. A class of finite graphs has degree sequences approximated by λ0,λ1,… if, for every i and n, the members of the class of size n have λi n + o(n) vertices of degree i. Our main result is a convergence law for random graphs with degree sequences approximated by some sequence λ0,λ1,…. With certain conditions on the sequence λ0,λ1,…, the probability of any first-order sentence on random graphs of size n converges to a limit as n grows.

REFERENCES

• 1: James Abello , Adam L. Buchsbaum , Jeffery Westbrook, A Functional Approach to External Graph Algorithms, Proceedings of the 6th Annual European Symposium on Algorithms, p.332-343, August 24-26, 1998
• 2: Serge Abiteboul , Kevin Compton , Victor Vianu, Queries are easier than you thought (probably), Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.23-32, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137105]
• 3: Adamic, L. A. and Huberman, B. A. 1999. Growth dynamics of the world wide web. Nature 401, 131.
• 4: Aiello, W., Chung, F., and Lu, L. 2001. A random graph model for power law graphs. Experimental Math 10, 53--66.
• 5: William Aiello , Fan Chung , Linyuan Lu, Random evolution in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 6: Anderson, R. M. and May, R. M. 1995. Susceptible-infectious-recovered epidemic models with dynamic partnerships. J. Math. Biology 33, 661--675.
• 7: Ball, F., Mollison, and Scalia-Tomba, G. 1997. Epidemics with two levels of mixing. Ann. Appl. Probab. 7, 46--89.
• 8: Barabási, A., Albert, R., and Jeong, H. 1999. Scale-free characteristics of random networks: The topology of the world wide web. Physica A 272, 173--187.
• 9: Bhalla, U. S. and Iyengar, R. 1999. Emergent properties of networks of biological signalling pathways. Science 283, 381--387.
• 10: Bollobás, B. 1985. Random Graphs. Academic Press, London.
• 11: Bower, J. M. and Bolouri, H. 2001. Computational Modeling of Genetic and Biochemical Networks. The MIT Press, Cambridge, MA.
• 12: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
• 13: Cohen, J. E., Briand, E., and Newman, C. M. 1990. Community Food Webs: Data and Theory. Springer-Verlag, Berlin.
• 14: Cohen, R., Erez, K., ben Avraham, D., and Havlin, S. 2000. Resilience of the Internet to random breakdowns. Phys. Rev. Lett. 85, 4626--4628.
• 15: Derrida, B. and Pomeau, Y. 1986. Random networks of automata: A simple annealed approximation. Europhys. Lett. 1, 45--49.
• 16: Ehrenfeucht, A. 1961. An application of games to the completeness problem for formalized theories. Fund. Math. 49, 129--141.
• 17: Erdős, P. and Rényi, A. 1959. On random graphs. Pub. Math 6, 290--297.
• 18: Erdős, P. and Rényi, A. 1960. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Kozl. 5, 17--61.
• 19: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, ACM SIGCOMM Computer Communication Review, v.29 n.4, p.251-262, Oct. 1999
• 20: Gaifman, H. 1982. On local and non-local properties. In Proceedings of the Herbrand Symposium Logic Colloquium '81. North Holland.
• 21: Gilbert, E. 1961. Random plane networks. J. SIAM 9, 533--543.
• 22: Glance, N. S. and Huberman, B. A. 1993. The outbreak of cooperation. J. Math. Soc. 17, 281--302.
• 23: Granovetter, M. 1978. Threshold models of collective behavior. Am. J. Soc. 83, 1420--1443.
• 24: Harris, T. E. 1989. The Theory of Branching Processes. Dover Publications, Inc., New York.
• 25: Kauffman, S. A. 1984. Emergent properties in random complex automata. Physica D 10, 145--156.
• 26: Kauffman, S. A. 1993. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, New York.
• 27: Keeling, M. J. 1999. The effects of local spatial structure on epidemiological invasions. Proc. Royal Soc. Lond. B 266, 859--867.
• 28: Kosterev, D. N., Taylor, C. W., and Mittelstadt, W. A. 1999. A model validation for the August 10, 1996 WSCC system outage. IEEE Trans. Power Systems 14, 967--979.
• 29: Kretschmar, M. and Morris, M. 1996. Measures of concurrency in networks and the spread of infectious disease. Math. Biosciences 133, 165--195.
• 30: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 31: Sérgio Lifschitz , Victor Vianu, A probabilistic view of Datalog parallelization, Theoretical Computer Science, v.190 n.2, p.211-239, Jan. 20, 1998 [doi>10.1016/S0304-3975(97)00091-1 ]
• 32: Łuczak, T. 1992. Sparse random graphs with a given degree sequence. In Random Graphs, Vol. 2, A. Freize and T. Łuczak, Eds. Wiley, New York, 165--182.
• 33: Lynch, J. F. 1985. Probabilities of sfirst-order sentences about unary functions. Trans. AMS 287, 543--568.
• 34: Lynch, J. F. 1992. Probabilities of sentences about very sparse random graphs. Random Struct. Alg. 3, 33--53.
• 35: Lynch, J. F. 2002. Critical points for random boolean networks. Physica D 172, 49--64.
• 36: McKay, B. D. 1985. Asymptotics for symmetric 0-1 matrices with prescribed row sums. Ars Combinatorica 19A, 15--25.
• 37: Michael Molloy , Bruce Reed, A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, v.6 n.2-3, p.161-179, March-May 1995
• 38: Michael Molloy , Bruce Reed, The Size of the Giant Component of a Random Graph with a Given Degree Sequence, Combinatorics, Probability and Computing, v.7 n.3, p.295-305, September 1998 [doi>10.1017/S0963548398003526]
• 39: Newman, M. E. J. 2001. The structure of scientific collaboration networks. Prod. Nat. Acad. Sci. 98, 404--409.
• 40: Newman, M. E. J., Strogatz, S. H., and Watts, D. J. 2001. Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026118.
• 41: Sattenspiel, L. and Simon, C. P. 1988. The spread and persistence of infectious diseases in structured populations. Math. Biosci. 90, 367--383.
• 42: Strogatz, S. H. 2001. Exploring complex networks. Nature 410, 268--276.
• 43: Valente, T. W. 1996. Social network thresholds in the diffusion of innovations. Social Netw. 18, 69--89.
• 44: Williams, R. J. and Martinez, N. D. 2000. Simple rules yield complex food webs. Nature 404, 180--183.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Model theory

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems; Generating functions
      G.2.2 Graph Theory

General Terms:
Theory

Keywords:
Finite model theory, random graphs