Sharp performance bounds for graph clustering via convex optimization
Sharp performance bounds for graph clustering via convex optimization
复制标题
通过凸优化实现图聚类的明显性能界限
DOI：
10.1109/icassp.2014.6855219
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
B. Hassibi
中科院分区：
文献类型：
--
作者：
Ramya Korlakai Vinayak;Samet Oymak;B. Hassibi
在图中寻找簇的问题出现在一些应用中，如社交网络、数据挖掘和计算机网络。通常采用的一种典型的凸优化方法是识别图的邻接矩阵的稀疏加低秩分解，其中(密集的)低秩分量表示簇。在本文中，我们尖锐地刻画了使用该方法成功识别集群的条件。特别地，我们引入了一个星团的“有效密度”来衡量它的重要性，我们找到了最小有效密度的显式上下界，该最小有效密度划分了这一技术的成败区域。我们的条件是关于(A)簇的大小，(B)图的稠密性，和(C)凸规划的正则化参数。我们还提供了大量的模拟来证实我们的理论发现。
The problem of finding clusters in a graph arises in several applications such as social networks, data mining and computer networks. A typical, convex optimization-approach, that is often adopted is to identify a sparse plus low-rank decomposition of the adjacency matrix of the graph, with the (dense) low-rank component representing the clusters. In this paper, we sharply characterize the conditions for successfully identifying clusters using this approach. In particular, we introduce the “effective density” of a cluster that measures its significance and we find explicit upper and lower bounds on the minimum effective density that demarcates regions of success or failure of this technique. Our conditions are in terms of (a) the size of the clusters, (b) the denseness of the graph, and (c) regularization parameter of the convex program. We also present extensive simulations that corroborate our theoretical findings.