The connectivity of graphs of graphs with self-loops and a given degree sequence
From MaRDI portal
Publication:3388902
DOI10.1093/COMNET/CNY008zbMATH Open1462.05202arXiv1701.04888OpenAlexW3102287158MaRDI QIDQ3388902FDOQ3388902
Publication date: 7 May 2021
Published in: Journal of Complex Networks (Search for Journal in Brave)
Abstract: `Double edge swaps' transform one graph into another while preserving the graph's degree sequence, and have thus been used in a number of popular Markov chain Monte Carlo (MCMC) sampling techniques. However, while double edge-swaps can transform, for any fixed degree sequence, any two graphs inside the classes of simple graphs, multigraphs, and pseudographs, this is not true for graphs which allow self-loops but not multiedges (loopy graphs). Indeed, we exactly characterize the degree sequences where double edge swaps cannot reach every valid loopy graph and develop an efficient algorithm to determine such degree sequences. The same classification scheme to characterize degree sequences can be used to prove that, for all degree sequences, loopy graphs are connected by a combination of double and triple edge swaps. Thus, we contribute the first MCMC sampler that uniformly samples loopy graphs with any given sequence.
Full work available at URL: https://arxiv.org/abs/1701.04888
Recommendations
- Making multigraphs simple by a sequence of double edge swaps
- New classes of degree sequences with fast mixing swap Markov chain sampling
- Uniform sampling of digraphs with a fixed degree sequence
- Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices
- The switch Markov chain for sampling irregular graphs and digraphs
Cited In (1)
This page was built for publication: The connectivity of graphs of graphs with self-loops and a given degree sequence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3388902)
