- 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

Weight-driven growing networks

T. Antal* and P. L. Krapivsky†

  • Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts 02215, USA

  • *On leave from Institute for Theoretical Physics–HAS, Eötvös University, Budapest, Hungary.
  • †Electronic address: paulk@bu.edu
PDF

Phys. Rev. E 71, 026103 – Published 8 February, 2005

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

Abstract

We study growing networks in which each link carries a certain weight (randomly assigned at birth and fixed thereafter). The weight of a node is defined as the sum of the weights of the links attached to the node, and the network grows via the simplest weight-driven rule: A newly added node is connected to an already existing node with the probability which is proportional to the weight of that node. We show that the node weight distribution n(w) has a universal tail, that is, it is independent of the link weight distribution: n(w)∼w−3 as w→∞. Results are particularly neat for the exponential link weight distribution when n(w) is algebraic over the entire weight range.

View figure in article

Article Text

References (29)

  1. S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW (Oxford University Press, Oxford, 2003); R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach (Cambridge University Press, Cambridge, 2004).
  2. P. Erdős and P. Rényi, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).
  3. B. Bollobás, Random Graphs (Academic, London, 1985).
  4. R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
  5. P. L. Krapivsky and S. Redner, Comput. Netw. 39, 277 (2002).
  6. M. E. J. Newman, SIAM Rev. 45, 167 (2003).
  7. M. E. J. Newman, Phys. Rev. E 64, 016131 (2001); 64, 016132 (2001).
  8. A.-L. Barabási, H. Jeong, Z. Neda, E. Ravasz, A. Schubert, and T. Vicsek, Physica A 311, 590 (2002).
  9. R. Guimera, M. Sales-Pardo, and L. A. N. Amaral, e-print cond-mat/0312535.
  10. A. Barrat, M. Barthélemy, and A. Vespignani, Proc. Natl. Acad. Sci. U.S.A. USA 101, 3747 (2004).
  11. L. R. Ford and D. R. Fulkerson, Flows in Networks (Princeton University Press, Princeton, NJ, 1962)
  12. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice Hall, Englewood Cliffs, NJ, 1993).
  13. P. G. Doyle and J. L. Snell, Random Walks and Electric Networks (Math. Assoc. Amer., Washington, D.C., 1984).
  14. L. de Arcangelis, S. Redner, and A. Coniglio, Phys. Rev. B 31, 4725 (1985); 34, 4656 (1986).
  15. R. Rammal, C. Tannous, P. Breton, and A.-M. S. Tremblay, Phys. Rev. Lett. 54, 1718 (1985).
  16. M. E. J. Newman, e-print cond-mat/0407503.
  17. E. Almaas, P. L. Krapivsky, and S. Redner, e-print cond-mat/0408295.
  18. S. H. Yook, H. Jeong, A.-L. Barabási, and Y. Tu, Phys. Rev. Lett. 86, 5835 (2001).
  19. J. D. Noh and H. Rieger, Phys. Rev. E 66, 066127 (2002).
  20. D. Zheng, S. Trimper, B. Zheng, and P. M. Hui, Phys. Rev. E 67, 040102(R) (2003).
  21. P. J. Macdonald, E. Almaas, and A.-L. Barabási, e-print cond-mat/0405688.
  22. A. Barrat, M. Barthélemy, and A. Vespignani, Phys. Rev. Lett. 92, 228701 (2004); Phys. Rev. E70, 066149 (2004).

  23. Negative weights are occasionally appropriate, e.g., they can represent animosity between individuals in a social network.

  24. The analyticity of the node weight distribution n(w) breaks down at integer values as is obvious from Eq. (4). Differentiating Eq. (4), one can express F(k−1)(w) via F(w), F(w−1),…,F(w−k+1). Since F(w) is continuous but not differentiable at w=1, the cumulative distribution is continuously differentiable k−1 times at w=k (implying that the weight distribution is continuously differentiable k−2 times).

  25. N is a discrete variable and Nw(N) are random variables. Treating N as a continuous variable and Nw(N) as the average values of the corresponding random variables is asymptotically exact when the weight is sufficiently small; see, e.g., P. L. Krapivsky and S. Redner, J. Phys. A 35, 9517 (2002) for the detailed analysis of these issues in the model where growth is governed by preferential attachment.

  26. For integer ν⩾4, the νth term in expansion (11) acquires a logarithmic correction; for ν=3, even the leading-order term has a logarithmic correction n(w)∼w−3ln(w).

  27. The expected value for the sum of k independent identically distributed random variables taken from the exponential distribution is w=k; in the present case, the average weight of the node of large degree is (slightly) higher since the growth is weight-driven.

  28. P. L. Krapivsky and S. Redner, Phys. Rev. E 63, 066123 (2001).
  29. P. L. Krapivsky, G. J. Rodgers, and S. Redner, Phys. Rev. Lett. 86, 5401 (2001).

Outline

Information

Phys. Rev. E 71, 026103– Published 8 February, 2005
  • Received 12 August 2004

© 2005 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation