### Skapa referens, olika format (klipp och klistra)

**Harvard**

Onsjö, M. (2005) *Some Graph Partitioning Algorithms based on belief propagation*. Göteborg : Chalmers University of Technology

** BibTeX **

@mastersthesis{

Onsjö2005,

author={Onsjö, Mikael},

title={Some Graph Partitioning Algorithms based on belief propagation},

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%.
},

publisher={Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers), Chalmers tekniska högskola},

place={Göteborg},

year={2005},

keywords={graph partitioning, partitioning, bi-categorical clustering, clustering, belief propagation, maximum likelihood},

note={61 pages},

}

** RefWorks **

RT Generic

SR Electronic

ID 23463

A1 Onsjö, Mikael

T1 Some Graph Partitioning Algorithms based on belief propagation

YR 2005

AB 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%.

PB Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers), Chalmers tekniska högskola,

LA eng

LK http://www.odinlake.net/Cvmain/documents/GraphPartitioning.pdf

OL 30