Document Open Access Logo

Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals

Authors Georgios Amanatidis, Pieter Kleer

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.7.pdf
  • Filesize: 0.77 MB
  • 23 pages

Document Identifiers

Author Details

Georgios Amanatidis
  • University of Essex, Colchester, UK
Pieter Kleer
  • Tilburg University, The Netherlands

Acknowledgements

Part of this work has been carried out while Pieter Kleer was a postdoctoral fellow at the Max Planck Institute for Informatics in Saarbrücken, Germany.

Cite As Get BibTex

Georgios Amanatidis and Pieter Kleer. Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.STACS.2023.7

Abstract

The approximate uniform sampling of graphs with a given degree sequence is a well-known, extensively studied problem in theoretical computer science and has significant applications, e.g., in the analysis of social networks. In this work we study a generalization of the problem, where degree intervals are specified instead of a single degree sequence. We are interested in sampling and counting graphs whose degree sequences satisfy the corresponding degree interval constraints. A natural scenario where this problem arises is in hypothesis testing on networks that are only partially observed. We provide the first fully polynomial almost uniform sampler (FPAUS) as well as the first fully polynomial randomized approximation scheme (FPRAS) for sampling and counting, respectively, graphs with near-regular degree intervals, i.e., graphs in which every node has a degree from an interval not too far away from a given r ∈ ℕ. In order to design our FPAUS, we rely on various state-of-the-art tools from Markov chain theory and combinatorics. In particular, by carefully using Markov chain decomposition and comparison arguments, we reduce part of our problem to the recent breakthrough of Anari, Liu, Oveis Gharan, and Vinzant (2019) on sampling a base of a matroid under a strongly log-concave probability distribution, and we provide the first non-trivial algorithmic application of a breakthrough asymptotic enumeration formula of Liebenau and Wormald (2017). As a more direct approach, we also study a natural Markov chain recently introduced by Rechner, Strowick and Müller-Hannemann (2018), based on three local operations - switches, hinge flips, and additions/deletions of an edge. We obtain the first theoretical results for this Markov chain, showing it is rapidly mixing for the case of near-regular degree intervals of size at most one.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
Keywords
  • graph sampling
  • degree interval
  • degree sequence
  • Markov Chain Monte Carlo method
  • switch Markov chain

Metrics

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

Related Versions

References

  1. Georgios Amanatidis and Pieter Kleer. Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 966-985. SIAM, 2019. Google Scholar
  2. Georgios Amanatidis and Pieter Kleer. Approximate sampling and counting of graphs with near-regular degree intervals. CoRR, abs/2110.09068, 2021. URL: https://doi.org/10.48550/arXiv.2110.09068.
  3. Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 35-46. IEEE Computer Society, 2018. Google Scholar
  4. Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 1-12, 2019. Google Scholar
  5. Mohsen Bayati, Jeong Han Kim, and Amin Saberi. A sequential algorithm for generating random graphs. Algorithmica, 58(4):860-910, 2010. Google Scholar
  6. Edward A. Bender and E. Rodney Canfield. The asymptotic number of labeled graphs with given degree sequences. Journal of Combinatorial Theory, Series A, 24(3):296-307, 1978. Google Scholar
  7. Ivona Bezáková, Nayantara Bhatnagar, and Eric Vigoda. Sampling binary contingency tables with a greedy start. Random Structures & Algorithms, 30(1-2):168-205, 2007. Google Scholar
  8. Joseph Blitzstein and Persi Diaconis. A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet mathematics, 6(4):489-522, 2011. Google Scholar
  9. Sergey G Bobkov and Prasad Tetali. Modified logarithmic Sobolev inequalities in discrete settings. Journal of Theoretical Probability, 19(2):289-336, 2006. Google Scholar
  10. Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1(4):311-316, 1980. Google Scholar
  11. Petter Brändén. Personal communication, 2020. Google Scholar
  12. Petter Brändén and June Huh. Lorentzian polynomials. Annals of Mathematics, 192(3):821-891, 2020. Google Scholar
  13. Sergio Caracciolo, Andrea Pelissetto, and Alan D. Sokal. Two remarks on simulated tempering. Unpublished manuscript, 1992. Google Scholar
  14. Corrie Jacobien Carstens and Pieter Kleer. Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence. In Proceedings of the 22nd International Conference on Randomization and Computation, RANDOM 2018, volume 116 of LIPIcs, pages 36:1-36:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  15. Anthony C.C. Coolen, Alessia Annibale, and Ekaterina Roberts. Generating random networks and graphs. Oxford university press, 2017. Google Scholar
  16. 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. Google Scholar
  17. Colin Cooper, Martin E. Dyer, and Catherine S. Greenhill. Corrigendum: Sampling regular graphs and a peer-to-peer network. CoRR, abs/1203.6111, 2012. URL: https://doi.org/10.48550/arXiv.1203.6111.
  18. Colin Cooper, Martin E. Dyer, Catherine S. Greenhill, and Andrew J. Handley. The flip Markov chain for connected regular graphs. Discrete Applied Mathematics, 2018. Google Scholar
  19. Mary Cryan, Heng Guo, and Giorgos Mousa. Modified log-Sobolev inequalities for strongly log-concave distributions. URL: https://doi.org/10.48550/arXiv.1903.06081.
  20. Martin E. Dyer, Catherine S. Greenhill, Pieter Kleer, James Ross, and Leen Stougie. Sampling hypergraphs with given degrees. Discret. Math., 344(11):112566, 2021. Google Scholar
  21. Péter L. Erdős, Ervin Győri, Tamaás Róbert Mezei, István Miklós, and Dániel Soltész. Half-graphs, other non-stable degree sequences, and the switch Markov chain. The Electronic Journal of Combinatorics, 28(3), 2021. Google Scholar
  22. Péter L. Erdős, Catherine S. Greenhill, Tamás Róbert Mezei, István Miklós, Daniel Soltész, and Lajos Soukup. The mixing time of switch Markov chains: A unified approach. Eur. J. Comb., 99:103421, 2022. Google Scholar
  23. Péter L. Erdős, Tamás Róbert Mezei, and István Miklós. Approximate sampling of graphs with near-p-stable degree intervals. CoRR, abs/2204.09493, 2022. URL: https://doi.org/10.48550/arXiv.2204.09493.
  24. Péter L. Erdős, Tamás Róbert Mezei, István Miklós, and Dániel Soltész. Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs. PLOS ONE, 13(8):1-20, August 2018. Google Scholar
  25. 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
  26. Tomás Feder, Adam Guetz, Milena Mihail, and Amin Saberi. A local switch Markov chain on given degree graphs with application in connectivity of peer-to-peer networks. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, pages 69-76. IEEE, 2006. Google Scholar
  27. Pu Gao and Nicholas C. Wormald. Uniform generation of random graphs with power-law degree sequences. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 1741-1758. SIAM, 2018. Google Scholar
  28. Pu Gao and Nilocas C. Wormald. Uniform generation of random regular graphs. SIAM Journal of Computing, 46(4):1395-1427, 2017. Google Scholar
  29. Catherine S. Greenhill and Matteo Sfragara. The switch Markov chain for sampling irregular graphs and digraphs. Theor. Comput. Sci., 719:1-20, 2018. Google Scholar
  30. Heng Guo, Mark Jerrum, and Jingcheng Liu. Uniform sampling through the Lovász local lemma. Journal of the ACM (JACM), 66(3):18, 2019. Google Scholar
  31. Leonid Gurvits. On multivariate Newton-like inequalities. In Advances in combinatorial mathematics, pages 61-78. Springer, 2009. Google Scholar
  32. Mark Jerrum, Brendan D. McKay, and Alistair Sinclair. When is a graphical sequence stable? Random Graphs, Vol. 2, pages 101-116, 1992. Google Scholar
  33. Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM Journal on Computing, 18(6):1149-1178, 1989. Google Scholar
  34. Mark Jerrum and Alistair Sinclair. Fast uniform generation of regular graphs. Theoretical Computer Science, 73(1):91-100, 1990. Google Scholar
  35. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51(4):671-697, 2004. Google Scholar
  36. 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
  37. Jeong Han Kim and Van H. Vu. Generating random regular graphs. Combinatorica, 26(6):683-708, 2006. Google Scholar
  38. Pieter Kleer. Sampling from the Gibbs distribution in congestion games. In Proceedings of the 22nd ACM Conference on Economics and Computation, EC 2021, pages 679-680. ACM, 2021. Google Scholar
  39. Anita Liebenau and Nick Wormald. Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph. CoRR, abs/1702.08373, 2017. URL: https://doi.org/10.48550/arXiv.1702.08373.
  40. Neal Madras and Dana Randall. Markov chain decomposition for convergence rate analysis. Ann. Appl. Probab., 12(2):581-606, May 2002. Google Scholar
  41. Russell A. Martin and Dana Randall. Disjoint decomposition of Markov chains and sampling circuits in Cayley graphs. Combinatorics, Probability & Computing, 15(3):411-448, 2006. Google Scholar
  42. Brendan D. McKay and Nicholas C. Wormald. Asymptotic enumeration by degree sequence of graphs of high degree. European Journal of Combinatorics, 11(6):565-580, 1990. Google Scholar
  43. Brendan D. McKay and Nicholas C Wormald. Uniform generation of random regular graphs of moderate degree. Journal of Algorithms, 11(1):52-67, 1990. Google Scholar
  44. 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
  45. Kazuo Murota. Discrete convex analysis. Mathematical Programming, 83(1-3):313-371, 1998. Google Scholar
  46. Kazuo Murota. Recent developments in discrete convex analysis. In Research Trends in Combinatorial Optimization, pages 219-260. Springer, 2009. Google Scholar
  47. Benjamin P. Olding and Patrick J. Wolfe. Inference for graphs and networks: Adapting classical tools to modern data. In Data Analysis for Network Cyber-Security, pages 1-31. World Scientific, 2014. Google Scholar
  48. Steffen Rechner, Linda Strowick, and Matthias Müller-Hannemann. Uniform sampling of bipartite graphs with degrees in prescribed intervals. Journal of Complex Networks, 6(6):833-858, 2018. Google Scholar
  49. Alistair Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing, 1:351-370, 1992. Google Scholar
  50. Angelika Steger and Nicholas C. Wormald. Generating random regular graphs quickly. Combinatroics, Probability & Computing, 8(4):377-396, 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