Some Graph Partitioning Algorithms based on belief propagation

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/23463
Download file(s):
There are no files associated with this item.
Type: Examensarbete för masterexamen
Master Thesis
Title: Some Graph Partitioning Algorithms based on belief propagation
Authors: Onsjö, Mikael
Abstract: In this thesis project we have focused on a kind of graph partitioning problem com- monly called bi-categorical clustering, however, we also show that all results are easily extended to general graph partitioning. In this problem we get a graph asked to output a partitioning and such that the partitions are of equal (or fixed given) size and so as to minimize the number of edges running between them. The problem is analyzed under an input model called the planted partitioning model since it has been shown that under a uniform distribution all feasible solution are likely to be equally good or very close. Under the planted partitioning model we find that it is natural to formulate the problem a bit differently and we therefore propose a new prob- lem, namely the Maximum Likelihood partitioning problem which given the observed graph from the known distribution, aims to find a ML solution. Our algorithms are derived using the well known belief propagation method. This method is very well suited for the scenario. Unfortunately, however, it is not yet well understood and therefore we must present our own analysis. Contrary, our research constitutes one of the first in-depth analysis of a specialized use of belief propagation. We present linear and quadratic time algorithms for solving the problem and show strong theoretical as well as experimental results. What we find is, in short, that when- ever the planted partitioning model is appropriate, our algorithm succeeds to nearly 100%.
Keywords: Datalogi;Computer science
Issue Date: 2005
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering, Computing Science (Chalmers)
URI: https://hdl.handle.net/20.500.12380/23463
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.