2025/06/05 by Maria Cherifa, Cherifa, Maria, Clément Calauzènes +3
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mobile Agent-Based Network Management #Network Security and Intrusion Detection #Security in Wireless Sensor Networks
paper · pdf · doi:10.48550/arxiv.2506.04921
openalex publication_date 2025/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
While online bipartite matching has gained significant attention in recent years, existing analyses in stochastic settings fail to capture the performance of algorithms on heterogeneous graphs, such as those incorporating inter-group affinities or other social network structures. In this work, we address this gap by studying online bipartite matching within the stochastic block model (SBM). A fixed set of offline nodes is matched to a stream of online arrivals, with connections governed probabilistically by latent class memberships. We analyze two natural algorithms: a \ttMyopic policy that greedily matches each arrival to the most compatible class, and the \ttBalance algorithm, which accounts for both compatibility and remaining capacity. For the \ttMyopic algorithm, we prove that the size of the matching converges, with high probability, to the solution of an ordinary differential equation (ODE), for which we provide a tractable approximation along with explicit error bounds. For the \ttBalance algorithm, we demonstrate convergence of the matching size to a differential inclusion and derive an explicit limiting solution. Lastly, we explore the impact of estimating the connection probabilities between classes online, which introduces an exploration-exploitation trade-off.