论文标题
重新访问光谱聚类：隐藏在Fiedler矢量中的信息
Spectral Clustering Revisited: Information Hidden in the Fiedler Vector
论文作者
论文摘要
我们对图表上的聚类问题感兴趣：众所周知，如果存在两个基础簇，那么与邻接矩阵的第二大特征值相对应的特征向量的符号可以可靠地重建两个群集。我们认为，特征向量的顶点分别具有最大和最小的条目，它与他们自己的群集的连接异常强烈，并且比其他分类更可靠地分类。这可以被视为热点猜想的离散版本，并且在应用程序中应该很有用。我们为随机块模型和几个示例提供了严格的证明。
We are interested in the clustering problem on graphs: it is known that if there are two underlying clusters, then the signs of the eigenvector corresponding to the second largest eigenvalue of the adjacency matrix can reliably reconstruct the two clusters. We argue that the vertices for which the eigenvector has the largest and the smallest entries, respectively, are unusually strongly connected to their own cluster and more reliably classified than the rest. This can be regarded as a discrete version of the Hot Spots conjecture and should be useful in applications. We give a rigorous proof for the stochastic block model and several examples.
