Belief propagation for graph partitioning

Abstract

We study the belief propagation algorithm for the graph bi-partitioning problem, i.e. the ground state of the ferromagnetic Ising model at a fixed magnetization. Application of a message passing scheme to a model with a fixed global parameter is not banal and we show that the magnetization can in fact be fixed in a local way within the belief propagation equations. Our method provides the full phase diagram of the bi-partitioning problem on random graphs, as well as an efficient heuristic solver that we anticipate to be useful in a wide range of application of the partitioning problem.

16 pages, 4 figures

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Elusive Glassy Phase in the Random Field Ising Model
• The cavity method at zero temperature
• Conjecture on the maximum cut and bisection width in random regular graphs

Cited by in corpus (12)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Universality of the stochastic block model
• Statistical physics approach to graphical games: local and global interactions
• Entropy Inflection and Invisible Low-Energy States: Defensive Alliance Example
• Optimal segmentation of directed graph and the minimum number of feedback arcs
• Bipartitioning of directed and mixed random graphs
• Cluster structure of optimal solutions in bipartitioning of small worlds
• Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
• Replica analysis of Franz-Parisi potential for sparse systems