- Access by Xinjiang University
Distance distribution in random graphs and application to network exploration
Phys. Rev. E 76, 066101 – Published 5 December, 2007
DOI: https://doi.org/10.1103/PhysRevE.76.066101
Abstract
We consider the problem of determining the proportion of edges that are discovered in an Erdős-Rényi graph when one constructs all shortest paths from a given source node to all other nodes. This problem is equivalent to the one of determining the proportion of edges connecting nodes that are at identical distance from the source node. The evolution of this quantity with the probability of existence of the edges exhibits intriguing oscillatory behavior. In order to perform our analysis, we introduce a different way of computing the distribution of distances between nodes. Our method outperforms previous similar analyses and leads to estimates that coincide remarkably well with numerical simulations. It allows us to characterize the phase transitions appearing when the connectivity probability varies.
Article Text
References (10)
- B. Bollobas, Random Graphs (Cambridge University Press, Cambridge, U.K., 2001).
- J. Travers and S. Milgram, Sociometry 32, 425 (1969).
- S. N. Dorogovtsev and J. F. F. Mendes. Evolution of Networks: From Biological Nets to the Internet and WWW (Oxford University Press, Oxford, 2003).
- D. J. Watts, Small Worlds: The Dynamics of Networks Between Order and Randomness (Princeton University Press, Princeton, NJ, 2003).
- S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin, Nucl. Phys. B 653, 307 (2003).
- A. Fronczak, P. Fronczak, and A. Janusz, Phys. Rev. E 70, 056110 (2004).
- J.-L. Guillaume and M. Latapy, Complex Syst. 16, 83 (2005).
- J. Sienkiewicz, P. Fronczak, and J. A. Holyst, e-print arXiv:cond-mat/0608273.
- A. Baronchelli and V. Loreto, Phys. Rev. E 73, 026103 (2006).
- S. Janson, T. Luczak, and A. Ruci, Random Graphs (Wiley-Interscience, New York, 2000).