Convex optimization for the planted k-disjoint-clique problem
Convex optimization for the planted k-disjoint-clique problem
复制标题
种植 k 不相交团问题的凸优化
DOI：
10.1007/s10107-013-0733-1
复制
发表时间：
2010
影响因子：
2.7
通讯作者：
S. Vavasis
中科院分区：
文献类型：
--
作者：
Brendan P. W. Ames;S. Vavasis
我们考虑$$k$$k-不相交-集团问题。输入是一个无向图$$G$$G，其中节点表示数据项，边表示相应项之间的相似性。问题是在图中找到覆盖最大节点数$$G$$G的$$k$$k不相交的团。这个问题可以理解为提出经典的“聚类”问题的一般方法。在聚类中，人们被给予数据项和距离函数，并且人们希望将数据划分成不相交的数据项的簇，使得每个簇中的项彼此接近。我们的公式还允许输入数据中存在不属于任何派系的“噪声”节点。$$k$$k-不相交团问题是NP-难的，但我们证明了对于以某种方式构造的输入实例，凸松弛可以在多项式时间内求解。我们的算法找到最优解的输入实例包括$$k$$k个不相交的大集团(称为‘种植集团’)，然后被随机插入或被对手插入的噪声边遮挡，以及不属于任何$$k$$k个种植集团的额外节点。
We consider the $$k$$k-disjoint-clique problem. The input is an undirected graph $$G$$G in which the nodes represent data items, and edges indicate a similarity between the corresponding items. The problem is to find within the graph $$k$$k disjoint cliques that cover the maximum number of nodes of $$G$$G. This problem may be understood as a general way to pose the classical ‘clustering’ problem. In clustering, one is given data items and a distance function, and one wishes to partition the data into disjoint clusters of data items, such that the items in each cluster are close to each other. Our formulation additionally allows ‘noise’ nodes to be present in the input data that are not part of any of the cliques. The $$k$$k-disjoint-clique problem is NP-hard, but we show that a convex relaxation can solve it in polynomial time for input instances constructed in a certain way. The input instances for which our algorithm finds the optimal solution consist of $$k$$k disjoint large cliques (called ‘planted cliques’) that are then obscured by noise edges inserted either at random or by an adversary, as well as additional nodes not belonging to any of the $$k$$k planted cliques.