On Realizations of a Joint Degree Matrix
arXiv:1302.3548 · doi:10.1016/j.dam.2014.10.012
Abstract
The joint degree matrix of a graph gives the number of edges between vertices of degree i and degree j for every pair (i,j). One can perform restricted swap operations to transform a graph into another with the same joint degree matrix. We prove that the space of all realizations of a given joint degree matrix over a fixed vertex set is connected via these restricted swap operations. This was claimed before, but there is an error in the previous proof, which we illustrate by example. We also give a simplified proof of the necessary and sufficient conditions for a matrix to be a joint degree matrix. Finally, we address some of the issues concerning the mixing time of the corresponding MCMC method to sample uniformly from these realizations.
12 pages, 2 figures
References in corpus (3)
Cited by in corpus (11)
- Quantifying randomness in real networks
- Exact sampling of graphs with prescribed degree correlations
- Reducing Degeneracy in Maximum Entropy Models of Networks
- Graphic Realizations of Joint-Degree Matrices
- Neighborhood degree lists of graphs
- A decomposition based proof for fast mixing of a Markov chain over balanced realizations of a joint degree matrix
- 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
- Mathematical Models for Predicting and Mitigating the Spread of Chlamydia Sexually Transmitted Infection
- Alice and the Caterpillar: A more descriptive null model for assessing data mining results