Systematic topology analysis and generation using degree correlations

ABSTRACT

Researchers have proposed a variety of metrics to measure important graph properties, for instance, in social, biological, and computer networks. Values for a particular graph metric may capture a graph's resilience to failure or its routing efficiency. Knowledge of appropriate metric values may influence the engineering of future topologies, repair strategies in the face of failure, and understanding of fundamental properties of existing networks. Unfortunately, there are typically no algorithms to generate graphs matching one or more proposed metrics and there is little understanding of the relationships among individual metrics or their applicability to different settings. We present a new, systematic approach for analyzing network topologies. We first introduce the dK-series of probability distributions specifying all degree correlations within d-sized subgraphs of a given graph G. Increasing values of d capture progressively more properties of G at the cost of more complex representation of the probability distribution. Using this series, we can quantitatively measure the distance between two graphs and construct random graphs that accurately reproduce virtually all metrics proposed in the literature. The nature of the dK-series implies that it will also capture any future metrics that may be proposed. Using our approach, we construct graphs for d=0, 1, 2, 3 and demonstrate that these graphs reproduce, with increasing accuracy, important properties of measured and modeled Internet topologies. We find that the d=2 case is sufficient for most practical purposes, while d=3 essentially reconstructs the Internet AS-and router-level topologies exactly. We hope that a systematic method to analyze and synthesize topologies offers a significant improvement to the set of tools available to network topology and protocol researchers.

REFERENCES

• 1: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 2: M. Boguòá and R. Pastor-Satorras. Class of correlated random networks with hidden variables. Physical Review E 68:036112, 2003.
• 3: M. Boguòá R. Pastor-Satorras, and A. Vespignani. Cut-offs and finite size effects in scale-free networks. European Physical Journal B 38:205--209, 2004.
• 4: T. Bu and D. Towsley. On distinguishing between Internet power law topology generators. In INFOCOM 2002.
• 5: CAIDA. Macroscopic topology AS adjacencies. http://www.caida.org/tools/measurement/skitter/asadjacencies.xml
• 6: H. Chang, S. Jamin, and W. Willinger. To peer or not to peer: Modeling the evolution of the Internet's AS-level topology. In INFOCOM 2006.
• 7: F. Chung and L. Lu. Connected components in random graphs with given degree sequences. Annals of Combinatorics 6:125--145, 2002.
• 8: F. K. R. Chung. Spectral Graph Theory volume 92 of Regional Conference Series in Mathematics American Mathematical Society, Providence, RI, 1997.
• 9: S. N. Dorogovtsev. Networks with given correlations. http://arxiv.org/abs/cond-mat/0308336v1
• 10: S. N. Dorogovtsev. Clustering of correlated networks. Physical Review E 69:027104, 2004.
• 11: S. N. Dorogovtsev , J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW (Physics), Oxford University Press, Inc., New York, NY, 2003
• 12: P. Erdós and A. Rényi. On random graphs. Publicationes Mathematicae 6:290--297, 1959.
• 13: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 14: P. Fraigniaud. A new perspective on the small-world phenomenon: Greedy routing in tree-decomposed graphs. In ESA 2005.
• 15: C. Gkantsidis, M. Mihail, and E. Zegura. The Markov simulation method for generating connected power law random graphs. In ALENEX 2003.
• 16: P. Harremoës. Binomial and Poisson distributions as maximum entropy distributions. Transactions on Information Theory 47(5):2039--041, 2001.
• 17: Internet Routing Registries. http://www.irr.net/.
• 18: D. Krioukov, K. Fall, and X. Yang. Compact routing on Internet-like graphs. In INFOCOM 2004.
• 19: Lun Li , David Alderson , Walter Willinger , John Doyle, A first-principles approach to understanding the internet's router-level topology, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 20: Priya Mahadevan , Dmitri Krioukov , Marina Fomenkov , Xenofontas Dimitropoulos , k c claffy , Amin Vahdat, The internet AS-level topology: three data sources and one definitive metric, ACM SIGCOMM Computer Communication Review, v.36 n.1, January 2006 [doi>10.1145/1111322.1111328]
• 21: S. Maslov, K. Sneppen, and A. Zaliznyak. Detection of topological patterns in complex networks:Correlation profile of the Internet. Physica A 333:529--540, 2004.
• 22: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: An Approach to Universal Topology Generation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.346, August 15-18, 2001
• 23: N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. Equation-of-state calculations by fast computing machines. Journal of Chemical Physics 21:1087, 1953.
• 24: Michael Molloy , Bruce Reed, A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, v.6 n.2-3, p.161-179, March-May 1995
• 25: M. E. J. Newman. Assortative mixing in networks. Physical Review Letters 89:208701, 2002.
• 26: University of Oregon RouteViews Project. http://www.routeviews.org/.
• 27: M. A. Serrano and M. Boguòá Tuning clustering in random networks with arbitrary degree distributions. Physical Review E 72:036133, 2005.
• 28: N. J. A. Sloane. Sequence A001349. The On-Line Encyclopedia of Integer Sequences. http://www.research.att.com/projects/OEIS?Anum=A001349
• 29: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 30: A. Vázquez, R. Pastor-Satorras, and A. Vespignani. Large-scale topological and dynamical properties of the Internet. Physical Review E 65:066130, 2002.
• 31: F. Viger and M. Latapy. Efficient and simple generation of random simple connected graphs with prescribed degree sequence. In COCOON 2005.
• 32: J. Winick and S. Jamin. Inet-3. 0:Internet topology generator. Technical Report UM-CSE-TR-456-02, University of Michigan, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

General Terms:
Design, Measurement, Theory

Keywords:
degree correlations, network topology