Exact sampling of graphs with prescribed degree correlations
arXiv:1503.06725 · doi:10.1088/1367-2630/17/8/083052
Abstract
Many real-world networks exhibit correlations between the node degrees. For instance, in social networks nodes tend to connect to nodes of similar degree. Conversely, in biological and technological networks, high-degree nodes tend to be linked with low-degree nodes. Degree correlations also affect the dynamics of processes supported by a network structure, such as the spread of opinions or epidemics. The proper modelling of these systems, i.e., without uncontrolled biases, requires the sampling of networks with a specified set of constraints. We present a solution to the sampling problem when the constraints imposed are the degree correlations. In particular, we develop an efficient and exact method to construct and sample graphs with a specified joint-degree matrix, which is a matrix providing the number of edges between all the sets of nodes of a given degree, for all degrees, thus completely specifying all pairwise degree correlations, and additionally, the degree sequence itself. Our algorithm always produces independent samples without backtracking. The complexity of the graph construction algorithm is O(NM) where N is the number of nodes and M is the number of edges.
arXiv comment25 pages, 7 figures
References in corpus (22)
- The structure and function of complex networks
- Assortative mixing in networks
- Random graphs with arbitrary degree distributions and their applications
- Mixing patterns in networks
- The structure and dynamics of multilayer networks
- Specificity and stability in topology of protein networks
- Dynamical and correlation properties of the Internet
- Generation of uncorrelated random scale-free networks
- Generating simple random graphs with prescribed degree distribution
- Cut-offs and finite size effects in scale-free networks
- Efficient and exact sampling of simple graphs with given arbitrary degree sequence
- All scale-free networks are sparse
- Robustness and Assortativity for Diffusion-like Processes in Scale-free Networks
- Unbiased sampling of network ensembles
- Minimum Dominating Sets in Scale-Free Network Ensembles
- Degree correlations in directed scale-free networks
- On Realizations of a Joint Degree Matrix
- On the swap-distances of different realizations of a graphical degree sequence
- Network Reliability: The effect of local network structure on diffusive processes
- Bias in generation of random graphs
- Endemic infections are always possible on regular networks
- A decomposition based proof for fast mixing of a Markov chain over balanced realizations of a joint degree matrix
Cited by in corpus (13)
- Quantifying randomness in real networks
- Network community detection using modularity density measures
- The configuration model for Barabasi-Albert networks
- Randomizing hypergraphs preserving degree correlation and local clustering
- Assortativity and leadership emergence from anti-preferential attachment in heterogeneous networks
- Neighborhood degree lists of graphs
- Grand canonical ensembles of sparse networks and Bayesian inference
- Connectedness matters: Construction and exact random sampling of connected graphs
- Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
- New classes of degree sequences with fast mixing swap Markov chain sampling
- An algebraic Monte-Carlo algorithm for the Partition Adjacency Matrix realization problem
- An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles
- Connected components in networks with higher-order interactions