Access by Xinjiang University

Bias in generation of random graphs

Hendrike Klein-Hennig and Alexander K. Hartmann^*

Institute of Physics, University of Oldenburg, D-26111 Oldenburg, Germany

^*a.hartmann@uni-oldenburg.de

Phys. Rev. E 85, 026101 – Published 2 February, 2012

DOI: https://doi.org/10.1103/PhysRevE.85.026101

Abstract

We study the statistical properties of the generation of random graphs according to the configuration model, in which one assigns randomly degrees to nodes. This model is often used, for example, for the scale-free degree distribution $\sim d^{- γ}$ . For the efficient variant, where nonfeasible edges are rejected and the construction of a graph continues, there exists a bias, which we calculate explicitly for a small sample ensemble. We find that this bias does not disappear with growing system size. This becomes visible, for example, also for scale-free graphs when measuring quantities such as the graph diameter. Hence the efficient generation of general scale-free graphs with a very broad distribution ( $γ < 2$ ) remains an open problem.

Article Text

References (32)

D. J. Watts, Small Worlds (Princeton University Press, Princeton, 1999).
R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW (Oxford University Press, New York, 2003).
M. E. J. Newman, SIAM Rev. 45, 167 (2003).
S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang, Phys. Rep. 424, 175 (2006).
M. E. J. Newman and A. L. Barabási, The Structure and Dynamics of Networks (Princeton University Press, Princeton, 2006).
A. K. Hartmann, Practical Guide to Computer Simulations (World Scientific, Singapore, 2009).
D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998).
D. J. Watts, Am. J. Sociol. 105, 493 (1999).
S. Redner, Eur. Phys. J. B 4, 131 (1998).
A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, Comput. Networks 33, 309 (2000).
A. L. Barabási, R. Albert, and H. Jeong, Physica A 281, 69 (2000).
H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási, Nature (London) 407, 651 (2000).
F. Liljeros, C. R. Edling, L. A. N. Amaral, H. E. Stanley, and Y. Aberg, Nature (London) 411, 901 (2001).
M. E. J. Newman, Contemp. Phys. 43, 323 (2005).
D. J. de Solla Price, J. Am. Soc. Inf. Sci. 27, 292 (1976).
A. L. Barabási and R. Albert, Science 286, 509 (1999).
S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin, Phys. Rev. Lett. 85, 4633 (2000).
P. L. Krapivsky and S. Redner, Phys. Rev. E 63, 066123 (2001).
M. Molloy and B. Reed, Rand. Struct. Algor. 6, 161 (1995).
E. Bender and R. Canfield, J. Comb. Theory, Ser. A 24, 296307 (1978).
B. Bóllobas, Eur. J. Comb. 1, 311 (1980).
M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. E 64, 026118 (2001).
T. Britton, M. Deijfen, and A. Martin-Löf, J. Stat. Phys. 124, 1377 (2006).
R. Milo, S. Shen-Orr, S. Itzkowitz, D. Chklovskii, and U. Alon, Science 298, 824 (2002).
M. Catanzaro, M. Boguná, and R. Pastor-Satorras, Phys. Rev. E 71, 027103 (2005).
O. D. King, Phys. Rev. E 70, 058101 (2004).
R. Taylor, SIAM Algor. Discr. Math. 3, 115 (1982).
C. I. Del Genio, H. Kim, Z. Toroczkai, and K. Bassler, PLoS ONE 5, e10012 (2010).
C. I. Del Genio, T. Gross, and K. E. Bassler, Phys. Rev. Lett. 107, 178701 (2011).
J. Blitzstein and P. Diaconis (unpublished) http://www.people.fas.harvard.edu/~blitz/BlitzsteinDiaconisGraphAlgorithm.pdf.
A. Coolen, A. De Martino, and A. Annibale, J. Stat. Phys. 136, 1035 (2009).

Physical Review E

Export citation

Export citation

Bias in generation of random graphs

Abstract

Article Text

References (32)

Outline

Information

Filter

Filter

Article Lookup

Enter a citation