Graph Clustering and Minimum Cut Trees
Graph Clustering and Minimum Cut Trees
复制标题
DOI：
10.1080/15427951.2004.10129093
复制
发表时间：
2004-01
影响因子：
--
通讯作者：
G. Flake;R. Tarjan;Kostas Tsioutsiouliklis
中科院分区：
文献类型：
--
作者：
G. Flake;R. Tarjan;Kostas Tsioutsiouliklis
在本文中，我们介绍了简单的图聚类方法的基础上最小割内的图。聚类方法足够通用，可以应用于任何类型的图，但非常适合链接结构暗示引用，相似性或认可概念的图，如Web和引用图。我们表明，所产生的集群的质量是有界的强最小切割和扩展标准。我们还开发了一个框架，层次聚类和现实世界的数据目前的应用程序。我们的结论是，聚类算法满足强有力的理论标准，并在实践中表现良好。
In this paper, we introduce simple graph clustering methods based on minimum cuts within the graph. The clustering methods are general enough to apply to any kind of graph but are well suited for graphs where the link structure implies a notion of reference, similarity, or endorsement, such as web and citation graphs. We show that the quality of the produced clusters is bounded by strong minimum cut and expansion criteria. We also develop a framework for hierarchical clustering and present applications to real-world data. We conclude that the clustering algorithms satisfy strong theoretical criteria and perform well in practice.