Internet Topology over Time
Preprint
Abstract
There are few studies that look closely at how the topology of the Internet evolves over time; most focus on snapshots taken at a particular point in time. In this paper, we investigate the evolution of the topology of the Autonomous Systems graph of the Internet, examining how eight commonly-used topological measures change from January 2002 to January 2010. We find that the distributions of most of the measures remain unchanged, except for average path length and clustering coefficient. The average path length has slowly and steadily increased since 2005 and the average clustering coefficient has steadily declined. We hypothesize that these changes are due to changes in peering policies as the Internet evolves. We also investigate a surprising feature, namely that the maximum degree has changed little, an aspect that cannot be captured without modeling link deletion. Our results suggest that evaluating models of the Internet graph by comparing steady-state generated topologies to snapshots of the real data is reasonable for many measures. However, accurately matching time-variant properties is more difficult, as we demonstrate by evaluating ten well-known models against the 2010 data.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Lord of the Links: A Framework for Discovering Missing Links in the Internet TopologyIEEE/ACM Transactions on Networking, 2008
- The Flattening Internet Topology: Natural Evolution, Unsightly Barnacles or Contrived Collapse?2008
- Characterization of complex networks: A survey of measurementsAdvances in Physics, 2007
- Towards a Theory of Scale-Free Graphs: Definition, Properties, and ImplicationsInternet Mathematics, 2005
- Accurately modeling the internet topologyPhysical Review E, 2004
- The Rich-Club Phenomenon in the Internet TopologyIEEE Communications Letters, 2004
- Mixing patterns in networksPhysical Review E, 2003
- Emergence of Scaling in Random NetworksScience, 1999
- Divergence measures based on the Shannon entropyIEEE Transactions on Information Theory, 1991
- Network structure and minimum degreeSocial Networks, 1983