Some Graph Partitioning Algorithms based on belief propagation
Examensarbete för masterexamen
Please use this identifier to cite or link to this item:
There are no files associated with this item.
|Type: ||Examensarbete för masterexamen|
|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 ﬁxed 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 ﬁnd 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 ﬁnd 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 ﬁrst 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 ﬁnd 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)
|Collection:||Examensarbeten för masterexamen // Master Theses|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.