Research Repository

Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices

Amanatidis, Georgios and Kleer, Pieter (2022) 'Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices.' SIAM Journal on Discrete Mathematics, 36 (1). pp. 118-146. ISSN 0895-4801

[img]
Preview
Text
SIDMA_JDM_mixing.pdf - Accepted Version

Download (601kB) | Preview

Abstract

The switch Markov chain has been extensively studied as the most natural Markov chain Monte Carlo approach for sampling graphs with prescribed degree sequences. In this work we study the problem of uniformly sampling graphs for which, in addition to the degree sequence, joint degree constraints are given. These constraints specify how many edges there should be between two given degree classes (i.e., subsets of nodes that all have the same degree). Although the problem was formalized over a decade ago, and despite its practical significance in generating synthetic network topologies, small progress has been made on the random sampling of such graphs. In the case of one degree class, the problem reduces to the sampling of regular graphs (i.e., graphs in which all nodes have the same degree), but beyond this very little is known. We fully resolve the case of two degree classes, by showing that the switch Markov chain is always rapidly mixing. We do this by combining a recent embedding argument developed by the authors in combination with ideas of Bhatnagar et al. [Algorithmica, 50 (2008), pp. 418--445] introduced in the context of sampling bichromatic matchings.

Item Type: Article
Uncontrolled Keywords: graph sampling; switch Markov chain; joint degree matrix
Divisions: Faculty of Science and Health
Faculty of Science and Health > Mathematical Sciences, Department of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 11 Feb 2022 17:02
Last Modified: 25 Apr 2022 14:59
URI: http://repository.essex.ac.uk/id/eprint/32272

Actions (login required)

View Item View Item