Statistical mechanics of bipartite $z$-matchings

Abstract

The matching problem has a large variety of applications including the allocation of competitive resources and network controllability. The statistical mechanics approach based on the cavity method has shown to be exact in characterizing this combinatorial problem on locally tree-like networks. Here we use the cavity method to solve the many-to-one bipartite $z$-matching problem that can be considered to be a model for the characterization of the capacity of user-server networks such as wireless communication networks. Finally we study the phase diagram of the model defined in network ensembles.

arXiv comment(7 pages, 1 figure)

References in corpus (15)

• The structure and dynamics of multilayer networks
• Percolation on sparse networks
• Bayesian inference of epidemics on networks via Belief Propagation
• Multiple percolation transitions in a configuration model of network of networks
• Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes
• Message passing theory for percolation models on multiplex networks with link overlap
• Optimal percolation on multiplex networks
• Control of Multilayer Networks
• Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
• Rare events and discontinuous percolation transitions
• Controllability and maximum matchings of complex networks
• Beauty and Distance in the Stable Marriage Problem
• Message-Passing Methods for Complex Contagions
• Maximum matching on random graphs
• Euclidean Matchings in Ultra-Dense Networks

Cited by in corpus (3)

• Controllability and maximum matchings of complex networks
• Phase transition in the bipartite z-matching
• A local algorithm and its percolation analysis of bipartite $z$-matching problem