Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 11 (2006) > Paper 33 open journal systems 

Stationary random graphs on Z with prescribed iid degrees and finite mean connections

Maria Deijfen, Stockholm University
Johan Jonasson, Chalmers University

Let F be a probability distribution with support on the non-negative integers. A model is proposed for generating stationary simple graphs on Z with degree distribution F and it is shown for this model that the expected total length of all edges at a given vertex is finite if F has finite second moment. It is not hard to see that any stationary model for generating simple graphs on Z will give infinite mean for the total edge length per vertex if F does not have finite second moment. Hence, finite second moment of F is a necessary and sufficient condition for the existence of a model with finite mean total edge length.

Full text: PDF | PostScript

Pages: 336-346

Published on: December 15, 2006

  1. Baum, E. and Katz, M (1965): Convergence rates in the law of large numbers, Trans. Amer. Math. Soc. 120 108-123, Math. Review 33#6679.
  2. Britton, T., Deijfen, M. and Martin-Löf, A. (2005): Generating simple random graphs with prescribed degree distribution, J. Stat. Phys. 124, 1377-1397.
  3. Chung, F. and Lu, L. (2002:1): Connected components in random graphs with given degrees sequences Ann. Comb. 6, 125-145, Math. Review 2003k:05123.
  4. Chung, F. and Lu, L. (2002:2): The average distances in random graphs with given expected degrees, Proc. Natl. Acad. Sci. 99, 15879-15882, Math. Review 22 #10924.
  5. Hofstad, R. van der, Hooghiemstra, G. and Znamenski, D. (2005): Random graphs with arbitrary iid degrees, preprint, (www.win.tue.nl/~rhofstad).
  6. Holroyd, A.E. and Peres, Y. (2003): Trees and Matchings from Point Processes, Electr. Commun. Probab. 8, 17-27. Math. Review 2004b:60127.
  7. Holroyd, A.E. and Peres, Y. (2005): Extra heads and invariant allocations, Ann. Probab. 33, 31-52, Math. Review 2005k:60153.
  8. Molloy, M. and Reed, B. (1995): A critical point for random graphs with a given degree sequence, Rand. Struct. Alg. 6, 161-179, Math. Review 97a:05191.
  9. Molloy, M. and Reed, B. (1998): The size of the giant component of a random graphs with a given degree sequence, Comb. Probab. Comput. 7, 295-305, Math. Review 2000c:05130.
  10. Newman (2003): The structure and function of complex networks, SIAM Rev. 45, 167-256, Math. Review 2005a:05206.
  11. Wormald, N.C. (1978): Some problems in the enumeration of labelled graphsm, Doctoral thesis, Newcastle University.

Support Tool
Capture Cite
View Metadata
Printer Friendly
Author Address
Email Author
Email Others

Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X