 |
|
|
| | | | | |
|
|
|
|
|
Stationary random graphs on Z with prescribed iid
degrees and finite mean connections
|
Maria Deijfen, Stockholm University
Johan Jonasson, Chalmers University
|
Abstract
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
Pages: 336-346
Published on: December 15, 2006
|
Bibliography
-
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.
-
Britton, T., Deijfen, M. and Martin-Löf, A. (2005):
Generating simple random graphs with prescribed degree
distribution, J. Stat. Phys. 124, 1377-1397.
-
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.
-
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.
-
Hofstad, R. van der, Hooghiemstra, G. and Znamenski, D.
(2005): Random graphs with arbitrary iid degrees, preprint, (www.win.tue.nl/~rhofstad).
-
Holroyd, A.E. and Peres, Y. (2003): Trees and Matchings
from Point Processes, Electr. Commun. Probab. 8, 17-27.
Math. Review 2004b:60127.
-
Holroyd, A.E. and Peres, Y. (2005): Extra heads and
invariant allocations, Ann. Probab. 33, 31-52,
Math. Review 2005k:60153.
-
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.
-
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.
-
Newman (2003): The structure and function of complex
networks, SIAM Rev. 45, 167-256,
Math. Review 2005a:05206.
-
Wormald, N.C. (1978): Some problems in the enumeration
of labelled graphsm, Doctoral thesis, Newcastle University.
|
|
|
|
|
|
|
|
| | | | |
Electronic Communications in Probability. ISSN: 1083-589X |
|
Context