A Connectivity-Prior Model for Generating Connected Power Law Random Graphs with Prescribed Degree Sequence

摘要

Generating precise network topologies is an important issue for the purpose of simulating and evaluating networking applications. Recent research results reveal that the topology of Internet is neither a purely random network nor a hierarchical structure, but similar to complex networks obeying power law distributions. Under this condition, a practical degree-driven method is widely used for generating network topologies with prescribed degree sequence. To import random features, additional random transformations are required to perform upon the generated graph. In this paper, we propose a connectivity-prior algorithm to create a connected graph and develop a simple but efficient method to perform randomization operations to transform the generated graph. During the creating and transforming process, the graph is kept connected. We made experiments with the latest degree sequence data of the actually Internet topologies. The results show that our method works more efficiently.