Document Open Access Logo

Speeding up Switch Markov Chains for Sampling Bipartite Graphs with Given Degree Sequence

Authors Corrie Jacobien Carstens, Pieter Kleer

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.36.pdf
  • Filesize: 486 kB
  • 18 pages

Document Identifiers

Author Details

Corrie Jacobien Carstens
  • Korteweg-de Vries Institute for Mathematics, Amsterdam, The Netherlands
Pieter Kleer
  • Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands

Funding

This work is supported by NWO Gravitation Project NETWORKS, Grant Number 024.002.003.

Cite As Get BibTex

Corrie Jacobien Carstens and Pieter Kleer. Speeding up Switch Markov Chains for Sampling Bipartite Graphs with Given Degree Sequence. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.36

Abstract

We consider the well-studied problem of uniformly sampling (bipartite) graphs with a given degree sequence, or equivalently, the uniform sampling of binary matrices with fixed row and column sums. In particular, we focus on Markov Chain Monte Carlo (MCMC) approaches, which proceed by making small changes that preserve the degree sequence to a given graph. Such Markov chains converge to the uniform distribution, but the challenge is to show that they do so quickly, i.e., that they are rapidly mixing.
The standard example of this Markov chain approach for sampling bipartite graphs is the switch algorithm, that proceeds by locally switching two edges while preserving the degree sequence. The Curveball algorithm is a variation on this approach in which essentially multiple switches (trades) are performed simultaneously, with the goal of speeding up switch-based algorithms. Even though the Curveball algorithm is expected to mix faster than switch-based algorithms for many degree sequences, nothing is currently known about its mixing time. On the other hand, the switch algorithm has been proven to be rapidly mixing for several classes of degree sequences.
In this work we present the first results regarding the mixing time of the Curveball algorithm. We give a theoretical comparison between the switch and Curveball algorithms in terms of their underlying Markov chains. As our main result, we show that the Curveball chain is rapidly mixing whenever a switch-based chain is rapidly mixing. We do this using a novel state space graph decomposition of the switch chain into Johnson graphs. This decomposition is of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
Keywords
  • Binary matrix
  • graph sampling
  • Curveball
  • switch
  • Markov chain decomposition
  • Johnson graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Annabell Berger and Matthias Müller-Hannemann. Uniform sampling of digraphs with a fixed degree sequence. In Graph Theoretic Concepts in Computer Science: 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers, pages 220-231, 2010. Google Scholar
  2. Ivona Bezáková, Nayantara Bhatnagar, and Dana Randall. On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries. In Computing and Combinatorics: 15th Annual International Conference, COCOON 2009 Niagara Falls, NY, USA, July 13-15, 2009 Proceedings, pages 307-316, 2009. Google Scholar
  3. Andries E. Brouwer and Willem H. Haemers. Spectra of graphs. Universitext. Springer New York, 2011. Google Scholar
  4. Corrie Jacobien Carstens, Annabell Berger, and Giovanni Strona. Curveball: a new generation of sampling algorithms for graphs with fixed degree sequence. CoRR, abs/1609.05137, 2016. URL: http://arxiv.org/abs/1609.05137.
  5. Corrie Jacobien Carstens and Pieter Kleer. Comparing the switch and curveball Markov chains for sampling binary matrices with fixed marginals. CoRR, abs/1709.07290, 2017. URL: http://arxiv.org/abs/1709.07290.
  6. Colin Cooper, Martin E. Dyer, and Catherine S. Greenhill. Sampling regular graphs and a peer-to-peer network. Combinatorics, Probability & Computing, 16(4):557-593, 2007. URL: http://dx.doi.org/10.1017/S0963548306007978.
  7. Persi Diaconis and Laurent Saloff-Coste. Comparison techniques for random walk on finite groups. The Annals of Probability, 21(4):2131-2156, 10 1993. Google Scholar
  8. Persi Diaconis and Laurent Saloff-Coste. Comparison theorems for reversible Markov chains. The Annals of Applied Probability, 3(3):696-730, 08 1993. URL: http://dx.doi.org/10.1214/aoap/1177005359.
  9. Persi Diaconis and Mehrdad Shahshahani. Time to reach stationarity in the Bernoulli-Laplace diffusion model. SIAM Journal on Mathematical Analysis, 18(1):208-218, 1987. Google Scholar
  10. Peter Donnelly, Peter Lloyd, and Aidan Sudbury. Approach to stationarity of the Bernoulli-Laplace diffusion model. Advances in Applied Probability, 26(3):715-727, 1994. Google Scholar
  11. Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, and Russell Martin. Markov chain comparison. Probab. Surveys, 3:89-111, 2006. Google Scholar
  12. Martin Dyer, Catherine Greenhill, and Mario Ullrich. Structure and eigenvalues of heat-bath Markov chains. Linear Algebra and its Applications, 454:57-71, 2014. Google Scholar
  13. Jack Edmonds. Paths, trees, and flowers. Canadian journal of mathematics, 17(3):449-467, 1965. Google Scholar
  14. Péter L. Erdős, Sándor Z. Kiss, István Miklós, and Lajos Soukup. Approximate counting of graphical realizations. PLOS ONE, 10(7):1-20, 2015. Google Scholar
  15. Péter L. Erdős, Tamás Róbert Mezei, and István Miklós. Efficiently sampling the realizations of irregular, but linearly bounded bipartite and directed degree sequences. CoRR, abs/1712.01709, 2017. URL: https://arxiv.org/abs/1712.01709.
  16. Péter L Erdős, István Miklós, and Zoltán Toroczkai. A decomposition based proof for fast mixing of a Markov chain over balanced realizations of a joint degree matrix. SIAM Journal on Discrete Mathematics, 29(1):481-499, 2015. Google Scholar
  17. Péter L. Erdős, István Miklós, and Zoltán Toroczkai. New classes of degree sequences with fast mixing swap Markov chain sampling. CoRR, abs/1601.08224, 2016. URL: http://arxiv.org/abs/1601.08224.
  18. Catherine S. Greenhill. A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs. Electronic Journal of Combinatorics, 18(1), 2011. Google Scholar
  19. Catherine S. Greenhill. Making Markov chains less lazy. CoRR, abs/1203.6668, 2013. URL: https://arxiv.org/abs/1203.6668.
  20. Catherine S. Greenhill. The switch Markov chain for sampling irregular graphs: extended abstract. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1564-1572, 2015. Google Scholar
  21. Catherine S. Greenhill and Matteo Sfragara. The switch Markov chain for sampling irregular graphs and digraphs. Theoretical Computer Science, 719:1-20, 2018. Google Scholar
  22. Derek A. Holton and John Sheehan. The Petersen graph. Cambridge University Press Cambridge, 1993. Google Scholar
  23. Ravi Kannan, Prasad Tetali, and Santosh Vempala. Simple Markov-chain algorithms for generating bipartite graphs and tournaments. Random Structures and Algorithms, 14(4):293-308, 1999. Google Scholar
  24. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2009. Google Scholar
  25. István Miklós, Péter L. Erdős, and Lajos Soukup. Towards random uniform sampling of bipartite graphs with given degree sequence. Electronic Journal of Combinatorics, 20(1), 2013. Google Scholar
  26. R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: simple building blocks of complex networks. Science, 298:824-827, 2002. URL: http://dx.doi.org/10.1126/science.298.5594.824.
  27. Jeremy Quastel. Diffusion of color in the simple exclusion process. Communications on Pure and Applied Mathematics, 45(6):623-679, 1992. URL: http://dx.doi.org/10.1002/cpa.3160450602.
  28. A. Ramachandra Rao, Rabindranath Jana, and Suraj Bandyopadhyay. A Markov chain Monte Carlo method for generating random (0, 1)-matrices with given marginals. Sankhyā: The Indian Journal of Statistics, Series A, 58(2):225-242, 1996. URL: http://dx.doi.org/10.2307/25051102.
  29. Alistair Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing, 1:351-370, 1992. Google Scholar
  30. G. Strona, D. Nappo, F. Boccacci, S. Fattorini, and J. San-Miguel-Ayanz. A fast and unbiased procedure to randomize ecological binary matrices with fixed row and column totals. Nature Communications, 5(4114), 2014. Google Scholar
  31. William T. Tutte. The factors of graphs. Canadian Journal of Mathematics, 4(3):314-328, 1952. Google Scholar
  32. Norman D. Verhelst. An efficient MCMC algorithm to sample binary matrices with fixed marginals. Psychometrika, 73(4):705, 2008. Google Scholar
  33. Fuzhen Zhang. Matrix theory: basic results and techniques. Universitext. Springer Berlin, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact