On the uniform generation of random graphs with prescribed degree sequences

By Ron Milo, Nadav Kashtan, Shalev Itzkovitz, Mark Newman, Uri Alon. 2003

375 citations recorded by the source corpus.

Random graphs with prescribed degree sequences have been widely used as a model of complex networks. Comparing an observed network to an ensemble of such graphs allows one to detect deviations from randomness in network properties. Here we briefly review two existing methods for the generation of random graphs with arbitrary degree sequences, which we call the ``switching'' and ``matching'' methods, and present a new method based on the ``go with the winners'' Monte Carlo method. The matching method may suffer from nonuniform sampling, while the switching method has no general theoretical bound on its mixing time. The ``go with the winners'' method has neither of these drawbacks, but is slow. It can however be used to evaluate the reliability of the other two methods and, by doing this, we demonstrate that the deviations of the switching and matching algorithms under realistic conditions are small compared to the ``go with the winners'' algorithm. Because of its combination of speed and accuracy we recommend the use of the switching method for most calculations.

Subfields: Computational Theory and Mathematics, Mathematical Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/2f41ca10c5f695091a399dcc551e99e6fe8a75e2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Mathematical Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Latent social structure in open source projects (2008, methodology): “We generated a large number(4) of random graphs with the same degree distribution as the observed networks using a rewiring approach [21, 44, 26].”
Bipartite Graphs as Models of Complex Networks (2003, background): “Moreover, some approaches exist [38, 44] which can easily be modiﬁed to obtain random bipartite graphs without multiples edges.”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, positive): “By doing the rewiring long enough, we obtain a random graph that has the same degree sequence as the original network [122].”
Influentials, Networks, and Public Opinion Formation (2007, background): “We have therefore also studied a series of “generalized random networks” (Milo et al. 2004; Newman, Strogatz, and Watts 2001), in which the influence distribution p (n) can be chosen arbitrarily.”
Inﬂuentials, Networks, and Public Opinion Formation (background): “We have therefore also studied a series of “generalized random networks” (Milo et al. 2004; Newman, Strogatz, and Watts 2001), in which the inﬂuence distribution p ( n ) can be chosen arbitrarily.”
Disrupted Modularity and Local Connectivity of Brain Functional Networks in Childhood-Onset Schizophrenia (2010, positive): “Enough iterations of this process ensure a randomized graph where every node still has the same degree as in the original graph (Milo et al., 2004).”
Network motifs in the transcriptional regulation network of Escherichia coli (2002, methodology): “I Rule of thumb: # Rewirings ' 10 × # edges [1].”