Based on the Belief Propagation Method,
we propose
simple and deterministic algorithms
for some NP-hard graph partitioning problems, such as the Most Likely Partition problem and the Graph Bisection problem.
These algorithms run in O(n+m) or O((n+m)log n) time on graphs with n vertices and m edges.
For their average case analysis,
we consider the planted solution model
and prove that
they yield an correct answer with high probability for large range of probabilistic parameters.