Algorithm : Greedy Spectral k-Clustering Input
Algorithm : Greedy Spectral k-Clustering Input
复制标题
算法：贪婪谱 k 聚类输入
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Anastasios Sidiropoulos
中科院分区：
文献类型：
--
作者：
T. Dey;Pan Peng;A. Rossi;Anastasios Sidiropoulos
一种流行的图聚类方法是考虑由其拉普拉斯矩阵的前k个特征向量所诱导的将输入图嵌入到R中，并在所得到的度量空间上通过几何操作来划分图。尽管这一方法在实践中取得了成功，但人们对遵循这一框架的几种启发式方法的理解有限。我们为自然的这种启发式算法提供了理论上的证明，这种启发式算法的某种形式已经被提出[BXKS11，NJW01]。我们的结果可以概括为以下几点。如果每个簇的外部电导很小，但内部电导很大，我们就说图的一个划分是强的。最近关于图划分的一个结果表明，对于具有足够大的谱间隙的图，存在强划分[OT14]。我们证明了特征向量在每个这样的强划分上围绕着它们的平均值聚集。将我们的结果与一个简单的k中心贪婪算法相结合，给出了所需的谱划分算法。我们证明了，对于拉普拉斯矩阵的第k个和第(k+1)个特征值之间有足够大的间隔的有界度图，该算法计算的划分接近于一个强划分。我们还展示了如何使用随机化在O(Nklogn)时间内实现这种针对k-中心的贪婪算法。最后，我们在一些真实世界和合成输入上对我们的算法进行了评估。∗部门俄亥俄州立大学计算机科学与工程系。俄亥俄州哥伦布，43210。邮箱：Tamaldey@cse.ohio-state.edu†俄亥俄州立大学计算机科学与工程系。俄亥俄州哥伦布，43210。邮箱：rossi.49@osU.S.edu‡计算机科学与工程系，以及系。俄亥俄州立大学数学系。俄亥俄州哥伦布，43201。电子邮件：sidiropoulos.1@osu edu 1 ar X iv：1 40 4.10 08 v3[S]2 6 N OV 2 01 4
A popular graph clustering method is to consider the embedding of an input graph into R induced by the first k eigenvectors of its Laplacian, and to partition the graph via geometric manipulations on the resulting metric space. Despite the practical success of this methodology, there is limited understanding of several heuristics that follow this framework. We provide theoretical justification for a natural such heuristic some form of which has been previously proposed [BXKS11, NJW01]. Our result can be summarized as follows. We say that a partition of a graph is strong if each cluster has small external conductance, but large internal conductance. A recent result on graph partitioning shows that strong partitions exist for graphs with sufficiently large spectral gap [OT14]. We prove that the eigenvectors cluster around their mean on each such strong partition. Combining our result with a simple greedy algorithm for k-centers gives us the desired spectral partitioning algorithm. We show that for bounded-degree graphs with a sufficiently large gap between the k-th and (k+1)-th eigenvalue of its Laplacian, this algorithm computes a partition that is close to a strong one. We also show how this greedy algorithm for k-center can be implemented in time O(nk log n) using randomization. Finally, we evaluate our algorithm on some real-world, and synthetic inputs. ∗Dept. of Computer Science and Engineering, The Ohio State University. Columbus, OH, 43210. tamaldey@cse.ohio-state.edu †Dept. of Computer Science and Engineering, The Ohio State University. Columbus, OH, 43210. rossi.49@osu.edu ‡Dept. of Computer Science and Engineering, and Dept. of Mathematics, The Ohio State University. Columbus, OH, 43201. sidiropoulos.1@osu.edu 1 ar X iv :1 40 4. 10 08 v3 [ cs .D S] 2 6 N ov 2 01 4