The mixing time of switch Markov chains: a unified approach. (English) Zbl 1476.60116
Summary: Since 1997 a considerable effort has been spent to study the mixing time of switch Markov chains on the realizations of graphic degree sequences of simple graphs. Several results were proved on rapidly mixing Markov chains on unconstrained, bipartite, and directed sequences, using different mechanisms.
The aim of this paper is to unify these approaches. We will illustrate the strength of the unified method by showing that on any \(P\)-stable family of unconstrained/bipartite/directed degree sequences the switch Markov chain is rapidly mixing. This is a common generalization of every known result that shows the rapid mixing nature of the switch Markov chain on a region of degree sequences. Among the applications of this general result is an almost uniform sampler for power-law and heavy-tailed degree sequences. Another application shows that the switch Markov chain on the degree sequence of an Erdős-Rényi random graph \(G(n,p)\) is asymptotically almost surely rapidly mixing if \(p\) is bounded away from 0 and 1 by at least \(\frac{5\log n}{n-1}\).
The aim of this paper is to unify these approaches. We will illustrate the strength of the unified method by showing that on any \(P\)-stable family of unconstrained/bipartite/directed degree sequences the switch Markov chain is rapidly mixing. This is a common generalization of every known result that shows the rapid mixing nature of the switch Markov chain on a region of degree sequences. Among the applications of this general result is an almost uniform sampler for power-law and heavy-tailed degree sequences. Another application shows that the switch Markov chain on the degree sequence of an Erdős-Rényi random graph \(G(n,p)\) is asymptotically almost surely rapidly mixing if \(p\) is bounded away from 0 and 1 by at least \(\frac{5\log n}{n-1}\).
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 05C07 | Vertex degrees |
| 05C80 | Random graphs (graph-theoretic aspects) |
Keywords:
switch Markov chainReferences:
| [1] | Albert, R.; Barabási, A.-L., Emergence of Scaling in Random Networks in Scientific, #5439 (1999) |
| [2] | Amanatidis, G.; Kleer, P., Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices, (Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 96 (2019)), 6-985 · Zbl 1431.60073 |
| [3] | Amanatidis, G.; Kleer, P., Rapid mixing of the switch Markov chain for strongly stable degree sequences, Random Struct. Algorithms, 57, 3, 21 (2020) · Zbl 1456.60175 |
| [4] | Berger, A.; Müller-Hannemann, M., Uniform sampling of digraphs with a fixed degree sequence, (Graph Theoretic Concepts in Computer Science, LNCS 6410 (2010), Springer: Springer Berlin) · Zbl 1309.68145 |
| [5] | Bezáková, I.; Bhatnagar, N.; Vigoda, E., Sampling binary contingency tables with a greedy start, Random Struct. Algorithms, 30, 1-2, 168-205 (2006) · Zbl 1104.62068 |
| [6] | Cooper, C.; Dyer, M.; Greenhill, C., Sampling regular graphs and a peer-to-peer network, Comb. Prob. Comp., 16, 4, 557-593 (2007) · Zbl 1137.05065 |
| [7] | Diaconis, P.; Graham, R.; Holmes, S. P., Statistical problems involving permutations with restricted positions, (State of the Art in Probability and Statistics (Lecture Notes-Monograph Series), 36 (2001)), 195-222 · Zbl 1373.62176 |
| [8] | Dyer, M.; Greenhill, C., Polynomial-time counting and sampling of two-rowed contingency tables, Theor. Comput. Sci., 246, 1, 265-278 (2000) · Zbl 0949.68009 |
| [9] | Dyer, M.; Jerrum, M.; Müller, H., On the switch Markov chain for perfect matchings, J. ACM, 64, 2, 33 (2017), # 12 · Zbl 1426.60097 |
| [10] | Erdős, P. L.; Király, Z.; Miklós, I., On the swap-distances of different realizations of a graphical degree sequence, Combin. Probab. Comput., 22, 3, 6-383 (2013) · Zbl 1263.05016 |
| [11] | Erdős, P. L.; Kiss, Z. S.; Miklós, I.; Soukup, L., Approximate counting of graphical realizations, PLOS ONE, 20 (2015), #E0131300 |
| [12] | Erdős, P. L.; Mezei, T. R.; Miklós, I., Efficiently sampling the realizations of irregular, but linearly bounded bipartite and directed degree sequences, 1-21 (2017), arXiv:1712.01709 |
| [13] | Erdős, P. L.; Mezei, T. R.; Miklós, I.; Soltész, D., Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs, PLOS One 2018, 1-19 (2018), # E0201995 |
| [14] | Gale, D., A theorem on flows in networks, Pacific J. Math., 7, 2, 1073-1082 (1957) · Zbl 0087.16303 |
| [15] | Gao, P.; Greenhill, C., Mixing time of the switch Markov chain and stable degree sequences, Discrete Appl. Math., 291, 143-162 (2021) · Zbl 1460.05038 |
| [16] | Gao, P.; Wormald, N., Enumeration of graphs with a heavy-tailed degree sequence, Adv. Math., 287, 412-450 (2016) · Zbl 1327.05155 |
| [17] | Gao, P.; Wormald, N., Uniform generation of random graphs with power-law degree sequences, (SIAM Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (2018)), 1741-1758 · Zbl 1403.05136 |
| [18] | Greenhill, C., A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs, Elec. J. Combin., 18, #P234 (2011) · Zbl 1243.05095 |
| [19] | C. Greenhill, The Switch Markov Chain for Sampling Irregular Graphs, in: Proc. 26th ACM-SIAM Symposium on Discrete Algorithms, New York-Philadelphia 2015, pp. 1564-1572. · Zbl 1371.60126 |
| [20] | Greenhill, C.; Sfragara, M., The switch Markov chain for sampling irregular graphs, Theoretical Comp. Sci, 719, 1-20 (2018) · Zbl 1395.60079 |
| [21] | Hakimi, S. L., On the realizability of a set of integers as degrees of the vertices of a simple graph, J. SIAM Appl. Math., 10, 496-506 (1962) · Zbl 0109.16501 |
| [22] | Havel, V., A remark on the existence of finite graphs. (in Czech), Časopis Pěst. Mat., 80, 477-480 (1955) · Zbl 0068.37202 |
| [23] | Jerrum, M.; McKay, B. D.; Sinclair, A., When is a graphical sequence stable?, (Frieze, A.; Luczak, T., Random Graphs, vol. 2 (1992), Wiley-Interscience), 101-116 · Zbl 0819.05052 |
| [24] | Jerrum, M.; Sinclair, A., Approximating the permanent, SIAM J. Comput., 18, 6 (1989) · Zbl 0723.05107 |
| [25] | Jerrum, M.; Sinclair, A., Fast uniform generation of regular graphs, Theor. Comput. Sci., 73, 1, 91-100 (1990) · Zbl 0694.68044 |
| [26] | Jerrum, M.; Sinclair, A.; Vigoda, E., A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, J. ACM, 51, 4, 671-697 (2004) · Zbl 1204.65044 |
| [27] | Jia, Tao; Barabási, A.-L., Control capacity and a random sampling method in exploring controllability of complex networks, (Scientific Reports, 3 (2013)), #2354 |
| [28] | R. Kannan, P. Tetali, S. Vempala, Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments, Extended Abstract, in: Proc. SODA ’97 1997, vol. 193-200. ISBN:0-89871-390-0. · Zbl 1321.05267 |
| [29] | Kleitman, D. J.; Wang, D. L., Algorithms for constructing graphs and digraphs with given valences and factors, Discrete Math., 6, 79-88 (1973) · Zbl 0263.05122 |
| [30] | Lamar, M. D., Directed 3-cycle anchored digraphs and their application in the uniform sampling of realizations from a fixed degree sequence, (S. Jain, R. R. Creasey; etal., ACM & IEEE & SCS Proc. of 2011 Winter Simulation Conference (2011)), 1-12 |
| [31] | Miklós, I.; Erdős, P. L.; Soukup, L., Towards random uniform sampling of bipartite graphs with given degree sequence, Electron. J. Combin., 20, 1, #P16 (2013), 1-49 · Zbl 1266.05155 |
| [32] | Morris, B.; Sinclair, A., Random walks on truncated cubes and sampling 0-1 Knapsack solutions, SIAM J. Comput., 34, 1, 195-226 (2004) · Zbl 1101.68044 |
| [33] | Petersen, J., Die Theorie Der Regularen Graphen, Acta Math., 15, 193-220 (1891) · JFM 23.0115.03 |
| [34] | Ryser, H. J., Combinatorial properties of matrices of zeros and ones, Canad. J. Math., 9, 371-377 (1957) · Zbl 0079.01102 |
| [35] | Sinclair, A., Improved bounds for mixing rates of Markov chains and multicommodity flow, Combin. Probab. Comput., 1, 351-370 (1992) · Zbl 0801.90039 |
| [36] | Štefankovič, D.; Vigoda, E.; Wilmes, J., On counting perfect matchings in general graphs, LATIN 2018, Theor. Inform., LNCS 10807, 873-885 (2018) · Zbl 1507.05051 |
| [37] | Yan, Gang; Vértes, P. E.; Towlson, E. K.; Chew, Yee Lian; Walker, D. S.; Schafer, W. R.; Barabási, A.-L., Network control principles predict neuron function in the Caenorhabditis elegans connectome, Nature, 550, 519-523 (2017) |
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.
