Graph Annotations in Modeling Complex Network Topologies
Graph Annotations in Modeling Complex Network Topologies
复制标题
DOI：
10.1145/1596519.1596522
复制
发表时间：
2009-10-01
影响因子：
0.9
通讯作者：
Riley, George
中科院分区：
文献类型：
--
作者：
Dimitropoulos, Xenofontas;Krioukov, Dmitri;Riley, George
复杂网络（如Internet）结构的粗略近似是一个简单的无向无权图。然而，这种近似失去了太多的细节。实际上，在这样的图中，由顶点和边表示的对象具有一些非平凡的内部结构，这些结构在不同类型的链接或节点之间变化并区分。在这项工作中，我们抽象的网络注释等额外的信息。我们引入了一个网络拓扑建模框架，将注释作为网络的扩展相关配置文件。假设我们有一个给定的网络测量这个配置文件，我们提出了一个算法来重新缩放它，以构建不同大小的网络，仍然再现原始测量的注释配置文件。使用这种方法，我们准确地捕捉网络应用程序和协议的现实模拟，或任何其他涉及复杂的网络拓扑结构，包括建模和模拟网络演进的模拟必不可少的网络属性。我们将我们的方法应用于自治系统（AS）的互联网拓扑结构与AS之间的业务关系注释。这种拓扑结构描述了互联网的大规模结构。深入了解这种结构和建模工具是研究未来互联网架构和设计的基石。我们发现，我们的技术是能够准确地捕捉结构的注释相关性在这个拓扑结构，从而再现了一些重要的属性，在合成生成的随机图。
The coarsest approximation of the structure of a complex network, such as the Internet, is a simple undirected unweighted graph. This approximation, however, loses too much detail. In reality, objects represented by vertices and edges in such a graph possess some nontrivial internal structure that varies across and differentiates among distinct types of links or nodes. In this work, we abstract such additional information as network annotations. We introduce a network topology modeling framework that treats annotations as an extended correlation profile of a network. Assuming we have this profile measured for a given network, we present an algorithm to rescale it in order to construct networks of varying size that still reproduce the original measured annotation profile. Using this methodology, we accurately capture the network properties essential for realistic simulations of network applications and protocols, or any other simulations involving complex network topologies, including modeling and simulation of network evolution. We apply our approach to the Autonomous System (AS) topology of the Internet annotated with business relationships between ASs. This topology captures the large-scale structure of the Internet. In depth understanding of this structure and tools to model it are cornerstones of research on future Internet architectures and designs. We find that our techniques are able to accurately capture the structure of annotation correlations within this topology, thus reproducing a number of its important properties in synthetically-generated random graphs.