- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Markov chain-based numerical method for degree distributions of growing networks

Dinghua Shi and Qinghua Chen*

Liming Liu†

  • Department of Mathematics, Shanghai University, Shanghai 200436, China

  • Department of Industrial Engineering and Engineering Management, Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong

  • *Also at College of Mathematics and Computer Science, Fujian Normal University, Fuzhou 350007, China.
  • †Electronic address: liulim@ust.hk
PDF

Phys. Rev. E 71, 036140 – Published 25 March, 2005

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

Abstract

In this paper, we establish a relation between growing networks and Markov chains, and propose a computational approach for network degree distributions. Using the Barabási-Albert model as an example, we first show that the degree evolution of a node in a growing network follows a nonhomogeneous Markov chain. Exploring the special structure of these Markov chains, we develop an efficient algorithm to compute the degree distribution numerically with a computation complexity of O(t2), where t is the number of time steps. We use three examples to demonstrate the computation procedure and compare the results with those from existing methods.

View figure in article

Article Text

References (22)

  1. R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
  2. S. H. Strogatz, Nature (London) 410, 268 (2001).
  3. P. Erdös and A. Rényi, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).
  4. D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998).
  5. S. Milgram, Psychol. Today 1, 60 (1967).
  6. R. Albert, H. Jeong, and A.-L. Barabási, Nature (London) 401, 130 (1999).
  7. A.-L. Barabási and R. Albert, Science 286, 509 (1999).
  8. A.-L. Barabási, R. Albert, and H. Jeong, Physica A 272, 173 (1999).
  9. R. Albert, H. Jeong, and A.-L. Barabási, Nature (London) 406, 378 (2000).
  10. M. Faloutsos, P. Faloutsos, and C. Faloutsos, Comput. Commun. Rev. 29, 251 (1999).
  11. R. Albert and A.-L. Barabási, Phys. Rev. Lett. 85, 5234 (2000).
  12. H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási, Nature (London) 407, 651 (2000).
  13. H. Jeong, S. P. Mason, A.-L. Barabási, and Z. N. Oltvai, Nature (London) 411, 41 (2001).
  14. S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin, Phys. Rev. Lett. 85, 4633 (2000).
  15. P. L. Krapivsky, S. Redner, and F. Leyvraz, Phys. Rev. Lett. 85, 4629 (2000).
  16. S. N. Dorogovtsev and J. F. F. Mendes, Phys. Rev. E 62, 1842 (2000).
  17. G. Bianconi and A.-L. Barabási, Phys. Rev. Lett. 86, 5632 (2001).
  18. E. Ravasz and A.-L. Barabási, e-print cond-mat/0206130.
  19. Q. H. Chen and D. H. Shi, Physica A 335, 240 (2004).
  20. S. N. Dorogovtsev and J. F. F. Mendes, Phys. Rev. E 63, 056125 (2001).
  21. S. M. Ross, Stochastic Processes (John Wiley and Sons, New York, 1983).
  22. D. H. Shi, J. L. Guo, and L. Liu, Matrix-Analytic Methods in Stochastic Models, edited by S. R. Chakravarthy and A. S. Alfa (Marcel Dekker, New York, 1996), p. 207.

Outline

Information

Phys. Rev. E 71, 036140– Published 25 March, 2005
  • Received 18 June 2004

© 2005 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation