Access by Xinjiang University

Statistics of weighted treelike networks

E. Almaas^1,*, P. L. Krapivsky^2,†, and S. Redner^2,‡

¹Center for Network Research and Department of Physics, University of Notre Dame, Notre Dame, Indiana 46617, USA
²Center for BioDynamics, Center for Polymer Studies, and Department of Physics, Boston University, Boston, Massachusetts 02215, USA

^*Electronic address: ealmaas@nd.edu
^†Electronic address: paulk@bu.edu
^‡Electronic address: redner@bu.edu

Phys. Rev. E 71, 036124 – Published 21 March, 2005

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

Abstract

We study the statistics of growing networks with a tree topology in which each link carries a weight ${(k_{i} k_{j})}^{θ}$ , where $k_{i}$ and $k_{j}$ are the node degrees at the end points of link $i j$ . Network growth is governed by preferential attachment in which a newly added node attaches to a node of degree $k$ with rate $A_{k} = k + λ$ . For general values of $θ$ and $λ$ , we compute the total weight of a network as a function of the number of nodes $N$ and the distribution of link weights. Generically, the total weight grows as $N$ for $λ > θ - 1$ and superlinearly otherwise. The link weight distribution is predicted to have a power-law form that is modified by a logarithmic correction for the case $λ = 0$ . We also determine the node strength, defined as the sum of the weights of the links that attach to the node, as function of $k$ . Using known results for degree correlations, we deduce the scaling of the node strength on $k$ and $N$ .

Article Text

References (23)

See, e.g., R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002); S. N. Dorogovtsev and J. F. F. Mendes, Adv. Phys. 51, 1079 (2002); 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, England, 2004).
M. E. J. Newman, Phys. Rev. E 64, 016131 (2001); 64, 016132 (2001).
A.-L. Barabási, H. Jeong, Z. Neda, E. Ravasz, A. Schubert, and T. Vicsek, Physica A 311, 590 (2002).
See R. Guimera, M. Sales-Pardo, and L. A. N. Amaral, e-print cond-mat/0312535 for a recent quantitative study of the airport network.
A. Barrat, M. Berthelemy, and A. Vespignani, Proc. Natl. Acad. Sci. U.S.A. 101, 3747 (2004); Phys. Rev. Lett. 92, 228701 (2004).
L. R. Ford and D. R. Fulkerson, Flows in Networks (Princeton University Press, Princeton, 1962).
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice Hall, Englewood Cliffs, NJ, 1993).
P. J. Macdonald, E. Almaas, and A.-L. Barabási, e-print cond-mat/0405688.
J. D. Noh and H. Rieger, Phys. Rev. E 66, 066127 (2002).
D. Zheng, S. Trimper, B. Zheng, and P. M. Hui, Phys. Rev. E 67, 040102(R) (2003).
M. E. J. Newman, Phys. Rev. E 70, 056131 (2004).
M. Baiesi and M. Paczuski, Nonlinear Processes Geophys. 12, 1 (2005).
A. E. Motter, C. Zhou, and J. Kurths, Europhys. Lett. 69, 334 (2005).
A. Barrat, M. Berthelemy, and A. Vespignani, Phys. Rev. E 70 066149 (2004).
T. Antal and P. L. Krapivsky, Phys. Rev. E 71, 026103 (2005).
P. L. Krapivsky and S. Redner, Phys. Rev. E 63, 066123 (2001).
A.-L. Barabási and R. Albert, Science 286, 509 (1999).
H. A. Simon, Biometrics 42, 425 (1955); reprinted in H. A. Simon, Models of Man (Wiley, New York, 1957).
P. L. Krapivsky and S. Redner, Comput. Netw. 39, 261 (2002).
P. L. Krapivsky and S. Redner, J. Phys. A 35, 9517 (2002).
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers (Oxford University Press, Oxford, 1979).
M. R. Schroeder, Number Theory in Science and Communication (Springer-Verlag, Berlin, 1986).
M. E. J. Newman, Phys. Rev. Lett. 89, 208701 (2002); Phys. Rev. E 67, 026126 (2003).

Physical Review E

Export citation

Export citation

Statistics of weighted treelike networks

Abstract

Article Text

References (23)

Outline

Information

Filter

Filter

Article Lookup

Enter a citation