Time series of Internet AS-level topology graphs: four patterns and one model

Abstract

Researchers have proposed a variety of Internet topology models. However almost all of them focus on generating one graph based on one single static source graph. On the other hand, Internet topology is evolving over time continuously with the addition and deletion of nodes and edges. If a model is based on all the topologies in the past, instead of one of them, it will be more accurate and closer to the real world topology. In this paper, we study the Internet As-level topology time-series from two different sources and find that both of them obey four same dynamic graph patterns. Then we propose a mode that can infer the topology in the future based on all the topologies in the past. Through theoretical and experimental analysis, we prove the topology that our model generates can match both the static and dynamic graph patterns. In addition, the parameters in the model are meaningful. Finally, we theoretically and experimentally prove that these parameters are directly related to some important graph characteristics.

9 pages, 4 figures

References in corpus (13)

• Emergence of scaling in random networks
• Evolution of networks
• Self-similarity of complex networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Topology of evolving networks: local events and universality
• Connectivity of Growing Random Networks
• Scale-Free Networks are Ultrasmall
• Origins of fractality in the growth of complex networks
• Self-similarity of complex networks and hidden metric spaces
• Accurately modeling the Internet topology
• Lessons from Three Views of the Internet Topology
• The Workshop on Internet Topology (WIT) Report
• Graph Annotations in Modeling Complex Network Topologies