Weighted Spectral Distribution for Internet Topology Analysis: Theory and Applications
- 9 September 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 18 (1) , 164-176
Abstract
Comparing graphs to determine the level of underlying structural similarity between them is a widely encountered problem in computer science. It is particularly relevant to the study of Internet topologies, such as the generation of synthetic topologies to represent the Internet's AS topology. We derive a new metric that enables exactly such a structural comparison: the weighted spectral distribution. We then apply this metric to three aspects of the study of the Internet's AS topology. i) We use it to quantify the effect of changing the mixing properties of a simple synthetic network generator. ii) We use this quantitative understanding to examine the evolution of the Internet's AS topology over approximately seven years, finding that the distinction between the Internet core and periphery has blurred over time. iii) We use the metric to derive optimal parameterizations of several widely used AS topology generators with respect to a large-scale measurement of the real AS topology.Keywords
This publication has 25 references indexed in Scilit:
- K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biasesNetworks and Heterogeneous Media, 2008
- Observing the evolution of internet as topologyACM SIGCOMM Computer Communication Review, 2007
- Characterising and modelling the internet topology — The rich-club phenomenon and the PFP modelBT Technology Journal, 2006
- The internet AS-level topologyACM SIGCOMM Computer Communication Review, 2006
- Assortative Mixing in NetworksPhysical Review Letters, 2002
- Structural graph matching using the EM algorithm and singular value decompositionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Topology of Evolving Networks: Local Events and UniversalityPhysical Review Letters, 2000
- A quantitative comparison of graph-based models for Internet topologyIEEE/ACM Transactions on Networking, 1997
- Routing of multipoint connectionsIEEE Journal on Selected Areas in Communications, 1988
- A Simplex Method for Function MinimizationThe Computer Journal, 1965