Weighted Spectral Distribution for Internet Topology Analysis: Theory and Applications
Weighted Spectral Distribution for Internet Topology Analysis: Theory and Applications
复制标题
DOI：
10.1109/tnet.2009.2022369
复制
发表时间：
2010-02
期刊：
影响因子：
--
通讯作者：
D. Fay;H. Haddadi;A. Thomason;A. Moore;R. Mortier;A. Jamakovic;S. Uhlig;M. Rio
中科院分区：
文献类型：
--
作者：
D. Fay;H. Haddadi;A. Thomason;A. Moore;R. Mortier;A. Jamakovic;S. Uhlig;M. Rio
在计算机科学中，比较图形以确定它们之间潜在结构相似性的水平是一个广泛遇到的问题。它与Internet拓扑的研究特别相关，例如生成表示Internet自治系统拓扑的合成拓扑。我们推导出一种新的度量，可以精确地进行这样的结构比较：加权谱分布。然后，我们将这个指标应用到Internet AS拓扑研究的三个方面。i)我们用它来量化改变一个简单的合成网络发生器的混合特性的影响。ii)我们使用这种定量的理解来检查互联网AS拓扑在大约七年的演变，发现随着时间的推移，互联网核心和外围之间的区别已经模糊。iii)我们使用度量来推导关于实际AS拓扑的大规模测量的几个广泛使用的AS拓扑生成器的最佳参数化。
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.