×

zbMATH — the first resource for mathematics

Metric structure of random networks. (English) Zbl 1010.05073
Summary: We propose a consistent approach to the statistics of the shortest paths in random graphs with a given degree distribution. This approach goes further than a usual tree ansatz and rigorously accounts for loops in a network. We calculate the distribution of shortest-path lengths (intervertex distances) in these networks and a number of related characteristics for the networks with various degree distributions. We show that in the large network limit this extremely narrow intervertex distance distribution has a finite width while the mean intervertex distance grows with the size of a network. The size dependence of the mean intervertex distance is discussed in various situations.

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C38 Paths and cycles
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bialas, P.; Burda, Z.; Petersson, B.; Tabaczek, J., Nucl. phys. B, 495, 463, (1997)
[2] Bialas, P.; Burda, Z.; Johnston, D., Nucl. phys. B, 493, 505, (1997)
[3] Catterall, S.; Kogut, J.; Renken, R., Phys. lett. B, 416, 274, (1998)
[4] Ambjørn, J.; Durhuus, B.; Jónsson, T., Phys. lett. B, 244, 403, (1990)
[5] Ambjørn, J.; Jurkiewicz, J., Nucl. phys. B, 451, 643, (1995)
[6] Strogatz, S.H., Nature, 401, 268, (2001)
[7] Albert, R.; Barabási, A.-L., Rev. mod. phys., 74, 47, (2002)
[8] Dorogovtsev, S.N.; Mendes, J.F.F., Adv. phys., 51, 1079, (2002)
[9] S.N. Dorogovtsev, J.F.F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW, Oxford Univ. Press, Oxford, 2003, in press · Zbl 1109.68537
[10] Albert, R.; Jeong, H.; Barabási, A.-L., Nature, 406, 378, (2000)
[11] Cohen, R.; Erez, K.; ben-Avraham, D.; Havlin, S., Phys. rev. lett., 85, 4626, (2000)
[12] Pastor-Satorras, R.; Vespignani, A., Phys. rev. lett., 86, 3200, (2001)
[13] Cohen, R.; Havlin, S.
[14] Puniyani, A.R.; Lukose, R.M.
[15] Newman, M.E.J.; Strogatz, S.H.; Watts, D.J., Phys. rev. E, 64, 026118, (2001)
[16] Newman, M.E.J., (), 35-68
[17] Bekessy, A.; Bekessy, P.; Komlos, J., Stud. sci. math. hungar., 7, 343, (1972)
[18] Bender, E.A.; Canfield, E.R., J. combin. theory A, 24, 296, (1978)
[19] Bollobás, B., Eur. J. combin., 1, 311, (1980)
[20] Wormald, N.C., J. combin. theory B, 31, 156, (1981), 168
[21] Molloy, M.; Reed, B., Random structures algorithms, 6, 161, (1995)
[22] Molloy, M.; Reed, B., Combin. probab. comput., 7, 295, (1998)
[23] Burda, Z.; Correia, J.D.; Krzywicki, A., Phys. rev. E, 64, 046118, (2002)
[24] Krzywicki, A.
[25] Dorogovtsev, S.N.; Mendes, J.F.F.; Samukhin, A.N.
[26] Berg, J.; Lässig, M.
[27] Dorogovtsev, S.N.; Goltsev, A.V.; Mendes, J.F.F., Phys. rev. E, 65, 066122, (2002)
[28] Szabó, G.; Alava, M.; Kertész, J., Phys. rev. E, 66, 026101, (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.