Belief propagation for graph partitioning

Petr Šulc, Lenka Zdeborová

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


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.

Original languageEnglish (US)
Article number285003
JournalJournal of Physics A: Mathematical and Theoretical
Issue number28
StatePublished - 2010
Externally publishedYes

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Modeling and Simulation
  • Mathematical Physics
  • General Physics and Astronomy


Dive into the research topics of 'Belief propagation for graph partitioning'. Together they form a unique fingerprint.

Cite this