Monte Carlo Wang-Landau algorithm and belief propagation for graph bipartitioning

Abstract

The division of graphs, as abstract descriptions of interacting components of a system, is one of the fundamental operations made on graphs, and it can be done using a great variety of algorithms. This work is focused on the division of a graph into two parts using inference methods. One of them is the Belief Propagation algorithm, known for its small runtime, specially when compared with Monte Carlo based methods. However, despite its success on the estimation of the partitioning cost lower bound in most of the situations, when it comes to determine the graph nodes that belong to each group so that such an optimal cost is obtained, the fast Belief Propagation approach tends to fail. In this context, it was developed a partitioning algorithm based on the Wang-Landau algorithm (a Monte Carlo method), that despite having a longer runtime is often more successful as a problem solver.

A divisão de grafos, como descrições abstratas de componentes que interagem num sistema, é uma das operações fundamentais em grafos, e pode ser feita usando uma grande variedade de algoritmos. Este trabalho está focado na divisão de um grafo em duas partes usando métodos de inferência. Um deles é o algoritmo de Belief Propagation, especialmente conhecido pelo seu curto tempo de execução, principalmente quando comparado com métodos de Monte Carlo. No entanto, apesar do seu sucesso na estimativa do limite inferior do custo de partição na maioria das situações, quando se trata de determinar os nós do grafo que pertencem a cada grupo de modo a que tal custo ótimo seja obtido, a abordagem rápida da Belief Propagation tende a falhar. Neste contexto, foi desenvolvido um algoritmo de partição baseado no algoritmo de Wang-Landau (um método de Monte Carlo), que apesar de ter um tempo de execução mais longo é frequentemente mais bem sucedido em solucionar problemas concretos.