Algorithms for  Graph Partitioning on the Planted Partition Model

植入性分割模型的图划分算法

ABSTRACT: The  NP-hard graph bisection problem is to partition the nodes of an undirected  graph into two equal-sized groups so as to minimize the number of edges that cross the  partition. The more general graph l-partition problem is to partition  the nodes of an undirected graph into l equal-sized groups so as to minimize  the total number of edges that cross between groups. We present a simple,  linear-time algorithm for the graph l-partition problem and we analyze it on  a random “planted l-partition” model. In this model, the n nodes of a graph  are partitioned into l groups, each of size n/l; two nodes in the same group  are connected by an edge with some probability p, and two nodes in different  groups are connected by an edge with some probability r < p. We show that  if p − r ≥ n−1/2+ǫ for some constant ǫ, then the algorithm finds the optimal  partition with probability 1 – exp（−n ^{Theta{(epsinlon)}}）.

作为NP-hard问题的图的二分问题就是将一个无向图分为两个相同大小的组而是的他们跨组的边的数量最小。更一般地，图的l-分割问题就是将一个无向图分割成l个相同大小的组从而使得组与组之间的边最小。我们提出了一个简单的，线性时间内的算法来解决l-分割问题；并且我们在一个随机的“植入性的l-分割”模型上分析了我们的算法。在这个模型中，图的n个节点被分割到l个组中，每个组的大小为n/l；两个在相同组里面的节点通过一个边以一定概率p相联系，两个不同组的节点通过一个边以r（r<p）链接。我们证明如果对一些常数epsinlon来说，那么这个算法找到最有分割的概率为。

这篇文章最大的贡献就是这个图分割产生的人工数据集的方法。如何产生l个模块的图，而不是作者提出的求解l分割的新方法。