Exact sampling of graphs with prescribed degree correlations
From MaRDI portal
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.
Recommendations
- Constructing and sampling directed graphs with given degree sequences
- Constructing and sampling graphs with a prescribed joint degree distribution
- A linear-time algorithm for sampling graphs with given degrees
- A sequential importance sampling algorithm for generating random graphs with prescribed degrees
- Uniform sampling of bipartite graphs with degrees in prescribed intervals
Cites work
- A critical point for random graphs with a given degree sequence
- A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
- A NEW MEASURE OF RANK CORRELATION
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A remark on the existence of finite graphs
- A sequential importance sampling algorithm for generating random graphs with prescribed degrees
- A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
- Complex networks: structure and dynamics
- Computing and Combinatorics
- Constructing and sampling directed graphs with given degree sequences
- Constructing and sampling graphs with a prescribed joint degree distribution
- Degree-based graph construction
- Generating simple random graphs with prescribed degree distribution
- scientific article; zbMATH DE number 1334601 (Why is no real title available?)
- scientific article; zbMATH DE number 1089130 (Why is no real title available?)
- Linear-time certifying algorithms for near-graphical sequences
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- On realizations of a joint degree matrix
- On the swap-distances of different realizations of a graphical degree sequence
- Relations between graphs and integer-pair sequences
- Sampling Regular Graphs and a Peer-to-Peer Network
- Switchings Constrained to 2-Connectivity in Simple Graphs
- The asymptotic number of labeled graphs with given degree sequences
- The Size of the Giant Component of a Random Graph with a Given Degree Sequence
- The Structure and Function of Complex Networks
- Towards random uniform sampling of bipartite graphs with given degree sequence
- Unbiased sampling of network ensembles
- Zero-one matrices with zero trace
Cited in
(15)- An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem
- Graphs with prescribed local neighborhoods of their universal coverings
- Neighborhood degree lists of graphs
- Exact sampling from perfect matchings of dense regular bipartite graphs
- Half sampling on bipartite graphs
- Construction of directed assortative configuration graphs
- Configuring random graph models with fixed degree sequences
- Network community detection using modularity density measures
- A perfect sampling method for exponential family random graph models
- Generating maximally disassortative graphs with given degree distribution
- Constructing and sampling directed graphs with given degree sequences
- Sampling graphs with a prescribed joint degree distribution using Markov chains
- Constructing and sampling graphs with a prescribed joint degree distribution
- Sequential stub matching for asymptotically uniform generation of directed graphs with a given degree sequence
- Feature-based network construction: from sampling to what-if analysis
This page was built for publication: Exact sampling of graphs with prescribed degree correlations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5151598)
