Abstract
We present a statistical analysis of different metrics characterizing the topological properties of Internet maps, collected at two different resolution scales: the router and the autonomous system level. The metrics we consider allow us to confirm the presence of scale-free signatures in several statistical distributions, as well as to show in a quantitative way the hierarchical nature of the Internet. Our findings are relevant for the development of more accurate Internet topology generators, which should include, along with the properties of the degree distribution, the hierarchical signatures reviewed in the present work.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
1. B. Bollobás, Modern Graph Theory, (Springer-Verlag, New York, 1998).
2. R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach, (Cambridge University Press, Cambridge, 2004).
3. M. Faloutsos, P. Faloutsos, and C. Faloutsos, ACM SIGCOMM ‘99, Comput. Commun. Rev. 29, 251 (1999).
4. R. Govindan and H. Tangmunarunkit, Proc. of IEEE Infocom 2000, Tel Aviv, Israel
5. G. Caldarelli, R. Marchetti, and L. Pietronero, Europhys. Lett. 52, 386 (2000).
6. R. Pastor-Satorras, A. Vázquez, and A. Vespignani, Phys. Rev. Lett. 87, 258701 (2001); A. Vázquez, R. Pastor-Satorras, and A. Vespignani, Phys. Rev. E 65, 066130 (2002).
7. W. Willinger, R. Govindan, S. Jamin, V. Paxson, and S. Shenker, Proc. Natl. Acad. Sci USA 99 2573, (2002)
8. H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, Comput. Commun. Rev. 32, 76 (2002)
9. Q. Chen, H. Chang, R. Govindan, S. Jamin, S. J. Shenker, and W. Willinger, Proceedings of IEEE Infocom 2002, New York, USA.
10. A. Broido and K. C. Claffy, San Diego Proceedings of SPIE International symposium on Convergence of IT and Communication. Denver, CO. 2001
11. D. Vukadinovic, P. Huang and T. Erlebach in Innovative Internet Computing Systems (I2CS 2002) Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2002.
12. R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
13. S. N. Dorogovtsev and J. F. F. Mendes, Evolution of networks: From biological nets to the Internet and WWW, (Oxford University Press, Oxford, 2003).
14. P. Erdös and P. Rényi, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).
15. B. Bollobás, Random graphs (Academic Press, London, 1095).
16. A. Medina, I. Matta, and J. Byers, Comput. Commun. Rev. 30, 2 (2000).
17. A. Medina and I. Matta, BRITE: a flexible generator of Internet topologies”, Tech. Rep. BU-CS-TR-2000-005, Boston University, 2000.
18. C. Jin, Q. Chen, and S. Jamin, “INET: Internet topology generators”, Tech. Rep. CSE-TR-433-00, EECS Dept., University of Michigan, 2000.
19. The National Laboratory for Applied Network Research (NLANR), sponsored by the National Science Foundation, provides Internet routing related information based on BGP data (see http://moat.nlanr.net/).
20. The Cooperative Association for Internet Data Analysis (CAIDA), located at the San Diego Supercomputer Center, provides measurements of Internet traffic metrics (see http://www.caida.org/home/).
21. Topology project, Electric Engineering and Computer Science Department, University of Michigan (http://topology.eecs.umich.edu/).
22. Mapping the Internet within the SCAN project at the Information Sciences Institute (http://www.isi.edu/div7/scan/).
23. B. Cheswick and H. Burch, Internet mapping project at Lucent Bell Labs (http://www.cs.bell-labs.com/who/ches/map/).
24. H. Burch and B. Cheswick, IEEE computer, 32, 97 (1999).
25. D. J. Watts and S. H. Strogatz, Nature 393, 440 (1998).
26. H. Chou, (http://xxx.lanl.gov/abs/cs.NI/0012019).
27. R. A. Albert, H. Jeong, and A.-L. Barabási, Nature 406, 378 (2000); D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. Lett. 85, 5468 (2000); R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett. 86, 3682 (2001).
28. R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. 86, 3200 (2001).
29. S. N. Dorogovtsev and J. F. F. Mendes, Advances in Physics 51, 1079 (2002).
30. L. A. N. Amaral, A. Scala, M. Barthélémy, and H. E. Stanley, Proc. Natl. Acad. Sci. USA 97, 11149 (2000).
31. S. Mossa, M. Barthélémy, H. E. Stanley, and L. A. N. Amaral, Phys. Rev. Lett. 88, 138701 (2002).
32. M. E. J. Newman, Phys. Rev. E 64, 016131-1 (2001); 64, 016132-1 (2001)
33. U. Brandes, Journal of Math. Sociology, 25, 35 (2001).
34. K.-I. Goh, B. Kahng, and D. Kim, Phys. Rev. Lett. 87, 278201 (2001).
35. E. Ravasz and A. Barabási, Phys. Rev. E 67, 026112 (2003).
36. K.-I. Goh, B. Kahng, and D. Kim, Phys. Rev. Lett. 88, 108701 (2002).
37. M. E. J. Newman, Phys. Rev. Lett. 89, 208701 (2002).
Author information
Authors and Affiliations
Editor information
Rights and permissions
About this chapter
Cite this chapter
Pastor-Satorras, R., Vázquez, A., Vespignani, A. Topology, Hierarchy, and Correlations in Internet Graphs. In: Ben-Naim, E., Frauenfelder, H., Toroczkai, Z. (eds) Complex Networks. Lecture Notes in Physics, vol 650. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-44485-5_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-44485-5_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22354-2
Online ISBN: 978-3-540-44485-5
eBook Packages: Springer Book Archive