On the uniform generation of random graphs with prescribed degree sequences
arXiv:cond-mat/0312028
Abstract
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.
References in corpus (5)
Cited by in corpus (37)
- Characterization of complex networks: A survey of measurements
- Bipartite Graphs as Models of Complex Networks
- Epidemic spreading on complex networks with community structures
- Identifying network communities with a high resolution
- The role of mentorship in protege performance
- SNAP: A General Purpose Network Analysis and Graph Mining Library
- Random Networks with Tunable Degree Distribution and Clustering
- Social Structure and Opinion Formation
- Constrained Markovian dynamics of random graphs
- Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure
- Exponential Random Graph models for Little Networks
- Designing Complex Networks
- The effect of scale-free topology on the robustness and evolvability of genetic regulatory networks
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- Generation of swine movement network and analysis of efficient mitigation strategies for African swine fever virus
- Are crossing dependencies really scarce?
- Learning Compatibility Across Categories for Heterogeneous Item Recommendation
- Biological Random Walks: multi-omics integration for disease gene prioritization
- Exact solutions for social and biological contagion models on mixed directed and undirected, degree-correlated random networks
- Assortative Mixing in Weighted Directed Networks
- Random Graphs with Prescribed -Core Sequences: A New Null Model for Network Analysis
- Uniform sampling of undirected and directed graphs with a fixed degree sequence
- Activity patterns on random scale-free networks: Global dynamics arising from local majority rules
- Marathon: An open source software library for the analysis of Markov-Chain Monte Carlo algorithms
- Biological Random Walks: integrating heterogeneous data in disease gene prioritization
- Rich-clubness test: how to determine whether a complex network has or doesn't have a rich-club?
- The Path-Star Transformation and its Effects on Complex Networks
- On the Role of Triadic Substructures in Complex Networks
- Mean field approximation for biased diffusion on Japanese inter-firm trading network
- A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
- Degree switching and partitioning for enumerating graphs to arbitrary orders of accuracy
- Generating realistic scaled complex networks
- Local Access to Huge Random Objects through Partial Sampling
- Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
- Motif Conservation Laws for the Configuration Model
- NoSPaM Manual - A Tool for Node-Specific Triad Pattern Mining
- On Cycles in the Transcription Network of Saccharomyces cerevisiae