LIPIcs.AofA.2024.16.pdf
- Filesize: 0.99 MB
- 21 pages
Document
Matching Algorithms in the Sparse Stochastic Block Model
Authors
Anna Brandenberger 
,
Byron Chin ,
Nathan S. Sheffield ,
Divya Shyamal
-
Part of:
Volume:
35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2024-07-18
File
Document Identifiers
Author Details
- Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA
Acknowledgements
We thank Elchanan Mossel for suggesting the problem, and David Jerison for helpful comments.
Cite As Get BibTex
Anna Brandenberger, Byron Chin, Nathan S. Sheffield, and Divya Shyamal. Matching Algorithms in the Sparse Stochastic Block Model. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
https://doi.org/10.4230/LIPIcs.AofA.2024.16
Abstract
In sparse Erdős-Rényi graphs, it is known that a linear-time algorithm of Karp and Sipser achieves near-optimal matching sizes asymptotically almost surely, giving a law-of-large numbers for the matching numbers of such graphs in terms of solutions to an ODE [Jonathan Aronson et al., 1998]. We provide an extension of this analysis, identifying broad ranges of stochastic block model parameters for which the Karp-Sipser algorithm achieves near-optimal matching sizes, but demonstrating that it cannot perform optimally on general stochastic block model instances. We also consider the problem of constructing a matching online, in which the vertices of one half of a bipartite stochastic block model arrive one-at-a-time, and must be matched as they arrive. We show that, when the expected degrees in all communities are equal, the competitive ratio lower bound of 0.837 found by Mastin and Jaillet for the Erdős-Rényi case [Andrew Mastin and Patrick Jaillet, 2013] is achieved by a simple greedy algorithm, and this competitive ratio is optimal. We then propose and analyze a linear-time online matching algorithm with better performance in general stochastic block models.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
Keywords
- Matching Algorithms
- Online Matching
- Stochastic Block Model
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Jonathan Aronson, Alan M. Frieze, and Boris G. Pittel. Maximum matchings in sparse random graphs: Karp-sipser revisited. Random Struct. Algorithms, 12:111-177, 1998.
-
Tom Bohman and Alan M. Frieze. Karp–sipser on random graphs with a fixed degree sequence. Combinatorics, Probability and Computing, 20:721-741, 2011.
- Thomas Budzinski, Alice Contat, and Nicolas Curien. The critical Karp-Sipser core of random graphs, 2022. URL: https://arxiv.org/abs/2212.02463.
- Byron Chin and Allan Sly. Optimal reconstruction of general sparse stochastic block models, 2021. URL: https://arxiv.org/abs/2111.00697.
- Jon Feldman, Aranyak Mehta, Vahab S. Mirrokni, and S. Muthukrishnan. Online stochastic matching: Beating 1-1/e. CoRR, abs/0905.4100, 2009. URL: https://arxiv.org/abs/0905.4100.
- Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109-137, 1983. URL: https://doi.org/10.1016/0378-8733(83)90021-7.
- Alexander E. Holroyd and James B. Martin. Galton–watson games. Random Structures & Algorithms, 59(4):495-521, 2021. URL: https://doi.org/10.1002/rsa.21008.
- Zhiyi Huang, Xinkai Shu, and Shuyi Yan. The power of multiple choices in online stochastic matching, 2022. URL: https://arxiv.org/abs/2203.02883.
- R. M. Karp and M. Sipser. Maximum matching in sparse random graphs. In 22nd Annual Symposium on Foundations of Computer Science (SFCS 1981), pages 364-375, 1981. URL: https://doi.org/10.1109/SFCS.1981.21.
-
Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. An optimal algorithm for on-line bipartite matching. In Symposium on the Theory of Computing, 1990.
- Kamer Kaya, Johannes Langguth, Ioannis Panagiotas, and Bora Uçar. Karp-Sipser based kernels for bipartite graph matching, pages 134-145. Society for Industrial and Applied Mathematics, 2020. URL: https://doi.org/10.1137/1.9781611976007.11.
- Johannes Langguth, Ioannis Panagiotas, and Bora Uçar. Shared-memory implementation of the karp-sipser kernelization process. In 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC), pages 71-80, 2021. URL: https://doi.org/10.1109/HiPC53243.2021.00021.
- Vahideh H. Manshadi, Shayan Oveis Gharan, and Amin Saberi. Online stochastic matching: Online actions based on offline statistics, 2011. URL: https://arxiv.org/abs/1007.1673.
- Andrew Mastin and Patrick Jaillet. Greedy online bipartite matching on random graphs. CoRR, abs/1307.2536, 2013. URL: https://arxiv.org/abs/1307.2536.
-
Elchanan Mossel, Joe Neeman, and Allan Sly. A proof of the block model threshold conjecture. Combinatorica, 38(3):665-708, 2018.
- Flore Sentenac, Nathan Noiry, Matthieu Lerasle, Laurent Ménard, and Vianney Perchet. Online matching in geometric random graphs, 2023. URL: https://arxiv.org/abs/2306.07891.
- Nahuel Soprano-Loto, Matthieu Jonckheere, and Pascal Moyal. Online matching for the multiclass stochastic block model, 2023. URL: https://arxiv.org/abs/2303.15374.
- Lutz Warnke. On wormald’s differential equation method, 2019. URL: https://arxiv.org/abs/1905.08928.
- Nicholas C. Wormald. Differential Equations for Random Processes and Random Graphs. The Annals of Applied Probability, 5(4):1217-1235, 1995. URL: https://doi.org/10.1214/aoap/1177004612.