The Markov Chain Simulation Method for Generating Connected Power Law Random Graphs

摘要

Graph models for real-world complex networks such as the Internet, the WWW and biological networks are necessary for analytic and simulation-based studies of network protocols, algorithms, engineering and evolution. To date, all available data for such networks suggest heavy tailed statistics, most notably on the degrees of the underlying graphs. 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 additional constraints, such as connectivity and randomness. Within the networking community, this is currently accepted as the most successful approach for modeling the inter-domain topology of the Internet. In this paper we propose a Markov chain simulation approach for generating a random connected graph with a given degree sequence. We introduce a novel heuristic to speed up the simulation of the Markov chain. We use metrics reminiscent of quality of service and congestion to evaluate the output graphs. We report experiments on degree sequences corresponding to real Internet topologies. All experimental results indicate that our method is efficient in practice, and superior to a previously used heuristic.