Abstract.
We investigate a problem of data packet transport between a pair of vertices on scale-free networks without loops or with a small number of loops. By introducing load of a vertex as accumulated sum of a fraction of data packets traveling along the shortest pathways between every pair of vertices, it is found that the load distribution follows a power law with an exponent \(\delta\). It is found for the Barabási-Albert-type model that the exponent \(\delta\) changes abruptly from \(\delta = 2.0\) for tree structure to \(\delta\simeq2.2\) as the number of loops increases. The load exponent seems to be insensitive to different values of the degree exponent \(\gamma\) as long as \(2 < \gamma < 3\).
Similar content being viewed by others
References
S.H. Strogatz, Nature (London) 410, 268 (2001)
R. Albert, A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002)
S.N. Dorogovtsev, J.F.F. Mendes, Evolution of Networks (Oxford University Press, Oxford, 2003)
M.E.J. Newman, SIAM Rev. 45, 167 (2003)
P. Erdös, A. Rényi, Publ. Math. Inst. Hung. Acad. Sci. Ser. A 5, 17 (1960)
R. Albert, H. Jeong, A.-L. Barabási, Nature (London) 401, 130 (1999)
B.A. Huberman, L.A. Adamic, Nature (London) 401, 131 (1999)
A. Broder et al. , Computer Networks 33, 309 (2000)
M. Faloutsos, P. Faloutsos, C. Faloutsos, Comput. Commun. Rev. 29, 251 (1999)
R. Pastor-Satorras, A. Vázquez, A. Vespignani, Phys. Rev. Lett. 87, 258701 (2001)
K.-I. Goh, B. Kahng, D. Kim, Phys. Rev. Lett. 88, 108701 (2002)
S. Redner, Eur. Phys. J. B 4, 131 (1998)
M.E.J. Newman, Proc. Natl. Acad. Sci. USA 98, 404 (2001)
A.-L. Barabási, H. Jeong, R. Ravasz, Z. Neda, T. Vicsek, A. Schubert, Physica A 311, 590 (2002)
H. Jeong, B. Tombor, R. Albert, Z.N. Oltvani, A.-L. Barabási, Nature (London) 407, 651 (2000)
A.-L. Barabási, R. Albert, Science 286, 509 (1999)
P.L. Krapivsky, S. Redner, F. Leyvraz, Phys. Rev. Lett. 85, 4629 (2000)
S.N. Dorogovtsev, J.F.F. Mendes, A.N. Samukhin, Phys. Rev. Lett. 85, 4633 (2000)
K.-I. Goh, B. Kahng, D. Kim, Phys. Rev. Lett. 87, 278701 (2001)
G. Caldarelli et al. , Phys. Rev. Lett. 89, 258702 (2002)
K.-I. Goh, E. Oh, H. Jeong, B. Kahng, D. Kim, Proc. Natl. Acad. Sci. USA 99, 12583 (2002)
L.C. Freeman, Sociometry 40, 35 (1977)
M.E.J. Newman, Phys. Rev. E 64, 016132 (2001)
U. Brandes, J. Math. Soc. 25, 163 (2001)
M.E.J. Newman, Phys. Rev. Lett. 89, 208701 (2002); M.E.J. Newman, Phys. Rev. E 67, 026126 (2003)
K.-I. Goh, E. Oh, B. Kahng, D. Kim, Phys. Rev. E 67, 017101 (2003)
M. Barthélemy, Phys. Rev. Lett. 91, 189803 (2003)
G. Szabó, M. Alava, J. Kertész, Phys. Rev. E 66, 026101 (2002)
J.D. Noh, Phys. Rev. E 67, 045103(R) (2003)
E. Ravasz, A.-L. Barabási, Phys. Rev. E 67, 026112 (2003)
S. Jung, S. Kim, B. Kahng, Phys. Rev. E 65, 056101 (2002)
H. Jeong, S.P. Mason, A.-L. Barabási, Z.N. Oltvai, Nature (London) 411, 41 (2001)
T. Ito et al. , Proc. Natl. Acad. Sci. USA 97, 1143 (1999); T. Ito et al. , Proc. Natl. Acad. Sci. USA 98, 4569 (2000)
B.A. Huberman, L.A. Adamic, e-print (cond-mat/9901071) (1999)
R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal, in Proc. IEEE FOCS 2000 (IEEE Computer Society Press, Los Alamitos, CA, 2000), pp. 57-65
S.N. Dorogovtsev, J.F.F. Mendes, Phys. Rev. E 63, 025101(R) (2001)
G. Bianconi, A.-L. Barabási, Europhys. Lett. 54, 436 (2001)
R. Solé, R. Pastor-Satorras, E. Smith, T. Kepler, Adv. Complex. Syst. 5, 43 (2002)
D. Meyer, University of Oregon Route Views Archive Project (http://archive.routeviews.org, 2001)
K.-I. Goh, C.-M. Ghim, B. Kahng, D. Kim, Phys. Rev. Lett. 91, 189804 (2003)
D. Jasnow, M. Wortis, Phys. Rev. 176, 739 (1968)
K.-I. Goh, B. Kahng, D. Kim, Physica A 318, 72 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: 4 February 2004, Published online: 14 May 2004
PACS:
89.75.Fb Structures and organization in complex systems - 05.65. + b Self-organized systems - 02.10.Ox Combinatorics; graph theory
Rights and permissions
About this article
Cite this article
Ghim, CM., Oh, E., Goh, KI. et al. Packet transport along the shortest pathways in scale-free networks. Eur. Phys. J. B 38, 193–199 (2004). https://doi.org/10.1140/epjb/e2004-00113-2
Published:
Issue Date:
DOI: https://doi.org/10.1140/epjb/e2004-00113-2