Rapid mixing of the switch Markov chain for strongly stable degree sequences. (English) Zbl 1456.60175
Summary: The switch Markov chain has been extensively studied as the most natural Markov chain Monte Carlo approach for sampling graphs with prescribed degree sequences. We show that the switch chain for sampling simple undirected graphs with a given degree sequence is rapidly mixing when the degree sequence is so-called strongly stable. Strong stability is satisfied by all degree sequences for which the switch chain was known to be rapidly mixing based on Sinclair’s multicommodity flow method up until a recent manuscript of P. Erdős et al. in [“The mixing time of the switch Markov chains: a unified approach”, Preprint, arXiv:1903.06600]. Our approach relies on an embedding argument, involving a Markov chain defined by M. Jerrum and A. Sinclair in [Theor. Comput. Sci. 73, No. 1, 91–100 (1990; Zbl 0694.68044)]. This results in a much shorter proof that unifies (almost) all the rapid mixing results for the switch chain in the literature, and extends them up to sharp characterizations of P-stable degree sequences. In particular, our work resolves an open problem posed by C. Greenhill and M. Sfragara in [Theor. Comput. Sci. 719, 1–20 (2018; Zbl 1395.60079)].
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
References:
| [1] | G.Amanatidis and P.Kleer, Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2‐class joint degree matrices. In Proceedings of the 30th Annual ACM‐SIAM Symposium on Discrete Algorithms, SODA 2019 (pp. 966-985), 2019. · Zbl 1431.60073 |
| [2] | M.Bayati, J.H.Kim, and A.Saberi, A sequential algorithm for generating random graphs, Algorithmica58 (2010), 860-910. · Zbl 1198.05138 |
| [3] | I.Bezáková, N.Bhatnagar, and E.Vigoda, Sampling binary contingency tables with a greedy start, Random Structures Algorithms30 (2007), 168-205. · Zbl 1104.62068 |
| [4] | B.Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, Eur. J. Combin.1 (1980), 311-316. · Zbl 0457.05038 |
| [5] | C.J.Carstens and P.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. volume 116 of LIPIcs (pp. 36:1-36:18), (2018). · Zbl 1522.60060 |
| [6] | C.Cooper, M.E.Dyer, and C.S.Greenhill, Sampling regular graphs and a peer‐to‐peer network, Combin. Probab. Comput.16 (2007), 557-593. · Zbl 1137.05065 |
| [7] | C.Cooper, M.E.Dyer, and C.S.Greenhill (2012). Corrigendum: Sampling regular graphs and a peer‐to‐peer network, CoRR, abs/1203.6111. |
| [8] | C.Cooper, M.E.Dyer, C.S.Greenhill, and A.J.Handley, The flip Markov chain for connected regular graphs, Discrete Appl. Math.254 (2018), 56-79. · Zbl 1404.05102 |
| [9] | C.I.Del Genio, H.Kim, Z.Toroczkai, and K.E.Bassler, Efficient and exact sampling of simple graphs with given arbitrary degree sequence, PLoS One5 (2010), 1-7. |
| [10] | M.Dyer, M.Jerrum, and H.Müller, On the switch Markov chain for perfect matchings, J. ACM64 (2017), 12:1-12:33. · Zbl 1426.60097 |
| [11] | P.L.Erdős, C.S.Greenhill, T.R.Mezei, I.Miklós, D.Soltész, and L.Soukup (2019). The mixing time of the swap (switch) Markov chains: A unified approach, CoRR, abs/1903.06600. |
| [12] | P.L.Erdős, Z.Király, and I.Miklós, On the swap‐distances of different realizations of a graphical degree sequence, Combin. Probab. Comput.22 (2013), 366-383. · Zbl 1263.05016 |
| [13] | P.L.Erdős, S.Z.Kiss, I.Miklós, and L.Soukup, Approximate counting of graphical realizations, PLoS One10 (2015), 1-20. |
| [14] | P.L.Erdős, T.R.Mezei, and I.Miklós (2017). Efficiently sampling the realizations of irregular, but linearly bounded bipartite and directed degree sequences, CoRR, abs/1712.01709. |
| [15] | P.L.Erdős, T.R.Mezei, I.Miklós, and D.Soltész, Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs, PLoS ONE13 (2018), 1-20. |
| [16] | P.L.Erdős, I.Miklós, and Z.Toroczkai, A decomposition based proof for fast mixing of a Markov chain over balanced realizations of a joint degree matrix, SIAM J. Discrete Math.29 (2015b), 481-499. · Zbl 1311.05084 |
| [17] | T.Feder, A.Guetz, M.Mihail, and A.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 (pp. 69-76), 2006. |
| [18] | T.Gallai and P.Erdos, Graphs with prescribed degree of vertices, Lapok11 (1960), 264-274. · Zbl 0103.39701 |
| [19] | P.Gao and C.S.Greenhill (2018). Uniform generation of spanning regular subgraphs of a dense graph, CoRR, abs/1807.00964. |
| [20] | P.Gao and N.Wormald, Enumeration of graphs with a heavy‐tailed degree sequence, Adv. n Math.287 (2016), 412-450. · Zbl 1327.05155 |
| [21] | P.Gao and N.C.Wormald, Uniform generation of random graphs with power‐law degree sequences. In Proceedings of the 29th Annual ACM‐SIAM Symposium on Discrete Algorithms, SODA 2018 (pp. 1741-1758), 2018. · Zbl 1403.05136 |
| [22] | P.Gao and N.C.Wormald, Uniform generation of random regular graphs, SIAM J. Comput.46 (2017), 1395-1427. · Zbl 1368.05133 |
| [23] | C.S.Greenhill, A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs, Electron. J. f Combin.18 (2011). · Zbl 1243.05095 |
| [24] | C.S.Greenhill, The switch Markov chain for sampling irregular graphs. In Proceedings of the 26th Annual ACM‐SIAM Symposium on Discrete Algorithms, SODA 2015 (pp. 1564-1572), 2015. · Zbl 1371.60126 |
| [25] | C.S.Greenhill and M.Sfragara, The switch Markov chain for sampling irregular graphs and digraphs, Theoret. Comput. Sci.719 (2018), 1-20. · Zbl 1395.60079 |
| [26] | S.Hakimi, On realizability of a set of integers as degrees of the vertices of a linear graph. I., J. Soc. Ind. Appl. Math.10 (1962), 496-506. · Zbl 0109.16501 |
| [27] | V.Havel, A remark on the existence of finite graphs, C̆asopis pro pĕstování matematiky80 (1955), 477-480. · Zbl 0068.37202 |
| [28] | M.Jerrum, B.D.McKay, and A.Sinclair, When is a graphical sequence stable?, Random Graphs2 (1992), 101-116. · Zbl 0819.05052 |
| [29] | M.Jerrum and A.Sinclair, Approximating the permanent, SIAM J. Comput.18 (1989), 1149-1178. · Zbl 0723.05107 |
| [30] | M.Jerrum and A.Sinclair, Fast uniform generation of regular graphs, Theoret. Comput. Sci.73 (1990), 91-100. · Zbl 0694.68044 |
| [31] | M.Jerrum, A.Sinclair, and E.Vigoda, A polynomial‐time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM51 (2004), 671-697. · Zbl 1204.65044 |
| [32] | R.Kannan, P.Tetali, and S.Vempala, Simple Markov‐chain algorithms for generating bipartite graphs and tournaments, Random Structures Algorithms14 (1999), 293-308. · Zbl 0933.05145 |
| [33] | J.H.Kim and V.H.Vu, Generating random regular graphs, Combinatorica26 (2006), 683-708. · Zbl 1121.05110 |
| [34] | D.A.Levin, Y.Peres, and E.L.Wilmer, Markov chains and mixing times. Amer. Math. Soc., Providence, RI, 2009. · Zbl 1160.60001 |
| [35] | B.D.McKay and N.C.Wormald, Uniform generation of random regular graphs of moderate degree, J. Algorithms11 (1990), 52-67. · Zbl 0711.68082 |
| [36] | B.D.McKay and N.C.Wormald, Asymptotic enumeration by degree sequence of graphs with degrees o(n^1/2), Combinatorica11 (1991), 369-382. · Zbl 0742.05047 |
| [37] | I.Miklós, P.L.Erdős, and L.Soukup, Towards random uniform sampling of bipartite graphs with given degree sequence, Electron. J. Combin.20. (2013), P16. · Zbl 1266.05155 |
| [38] | B.P.Olding and P.J.Wolfe, Inference for graphs and networks: Adapting classical tools to modern data. In Data Analysis for Network Cyber‐Security (pp. 1-31), 2014. |
| [39] | J.Petersen, Die theorie der regulären graphs, Acta Math.15 (1891), 193-220. · JFM 23.0115.03 |
| [40] | A.Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow, Combin. Probab. Comput.1 (1992), 351-370. · Zbl 0801.90039 |
| [41] | D.Štefankovič, E.Vigoda, and J.Wilmes, On counting perfect matchings in general graphs. In Proceedings of the 13th Latin American Symposium on Theoretical Informatics, LATIN 2018 (pp. 873-885), 2018. · Zbl 1507.05051 |
| [42] | A.Steger and N.C.Wormald, Generating random regular graphs quickly, Combin. Probab. Comput.8 (1999), 377-396. · Zbl 0935.05082 |
| [43] | R.Taylor, Constrained switchings in graphs. In Proceedings of the 8th Australian Conference on Combinatorial Mathematics (pp. 314-336), 1981. · Zbl 0484.05055 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
