Exact sampling of graphs with prescribed degree correlations

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.

25 pages, 7 figures

References in corpus (5)

• The structure and dynamics of multilayer networks
• Generating simple random graphs with prescribed degree distribution
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• Unbiased sampling of network ensembles
• Degree correlations in directed scale-free networks

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