On Generating Graphs with Prescribed Vertex Degrees for Complex Network Modeling 1
On Generating Graphs with Prescribed Vertex Degrees for Complex Network Modeling 1
复制标题
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
M. Mihail;Nisheeth K. Vishnoi
中科院分区：
文献类型：
--
作者：
M. Mihail;Nisheeth K. Vishnoi
现实世界复杂网络（例如互联网、万维网和生物网络）的图模型对于基于模拟的各种问题的研究是必要的。目前，此类网络有相当多的可用数据，但这些网络如何增长和演化的基本原理尚不清楚。从积极的一面来看，现有数据表明稳健且持久的重尾统计数据，尤其是在网络拓扑的程度方面。因此，生成满足观测数据的网络拓扑的实用方法是以下度驱动方法：首先通过从可用数据推断来预测图的度，然后构建满足度序列以及可能的附加约束（例如连通性、随机性、低成本等）的图。特别是，在网络社区内，这目前被认为是对互联网拓扑进行建模的最成功的方法。构造满足给定度序列的简单图是图论和理论计算机科学中的经典问题。这个问题与匹配理论密切相关，因此，该问题的许多概括也可以在严格的理论框架中得到解决。在本文中，我们回顾了一系列与度驱动网络生成方法相关的理论原语。其中一些原语可以很容易地在实践中进行调整，并丰富现有网络拓扑生成器的输出。更重要的是，我们形式化了几个理论问题，对于这些问题，有效的算法可以极大地影响应用程序环境。由于实际应用涉及数万个节点，近似算法就显得尤为重要。因此，我们希望本文能够引起网络建模界对一些相关经典图论的关注，并引起数学家和理论计算机科学家对各种新问题的关注，这些问题的解决可能会产生直接的实际影响。研究由 NSF-ITR-0220343 和佐治亚理工学院伊登菲尔德教员奖学金支持。
Graph models for real-world complex networks such as the Internet, the WWW and biological networks are necessary for simulation-based studies of a variety of problems. Currently, there is a fair amount of available data for such networks, and yet, the primitives of how these networks grow and evolve are not well understood. On the positive side, the available data suggest robust and persistent heavy tailed statistics, most notably on the degrees of the network topologies. Consequently, a practical way to generate network topologies that meet the observed data is the following degree-driven approach: First predict the degrees of the graph by extrapolation from the available data, and then construct a graph meeting the degree sequence and, possibly, additional constraints such as connectivity, randomness, low cost, to name a few. In particular, within the networking community, this is currently accepted as the most successful approach for modeling the topology of the Internet. Constructing a simple graph that meets a given degree sequence is a classical problem in graph theory and theoretical computer science. This problem is intimately related to the theory of matchings, and hence, many generalizations of the problem can be also addressed in a strict theoretical framework. In this paper we review a range of theoretical primitives that are relevant to the degree-driven network generation approach. Some of these primitives can be readily adapted in practice, and enrich the output of existing network topology generators. More importantly, we formalize several theoretical problems for which efficient algorithms can greatly impact the application context. Since the practical applications involve tens of thousands of nodes, approximation algorithms become particularly important. We thus hope that this paper will bring to the attention of the network modeling community some relevant classical graph theory, as well as bring to the attention of mathematicians and theoretical computer scientists a variety of new problems whose resolution may have direct practical impact. Research supported by NSF-ITR-0220343, and by a Georgia Tech Edenfield Faculty Fellowship.