Clustering Social Networks Using Distance-Preserving Subgraphs
Clustering Social Networks Using Distance-Preserving Subgraphs
复制标题
使用保持距离的子图对社交网络进行聚类
DOI：
10.1109/asonam.2010.78
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
P. Tan
中科院分区：
文献类型：
--
作者：
Ronald Nussbaum;A. Esfahanian;P. Tan
聚类分析描述了将数据集划分为相关对象的子集，这些子集通常是不相交的。不同类型的聚类算法之间存在相当大的差异。其中一些聚类算法将数据集表示为图，并使用基于图的属性来生成聚类。然而，许多图的属性并没有作为聚类算法的基础进行研究。在图论中，如果子图中每对顶点之间的距离（最短路径的长度）与原始图中的相应距离相同，则图的子图是距离保持的。在本文中，我们考虑了寻找适当的距离保持子图的问题，以及将一个简单图划分为任意数目的距离保持子图的聚类问题。基于距离保持子图的概念，我们还提出了一种称为DP-Cluster的聚类算法。大量使用图论的一个研究领域是对社会网络的分析。出于这个原因，我们评估了DP-Cluster在两个真实社会网络数据集上的性能。
Cluster analysis describes the division of a dataset into subsets of related objects, which are usually disjoint. There is considerable variety among the different types of clustering algorithms. Some of these clustering algorithms represent the dataset as a graph, and use graph-based properties to generate the clusters. However, many graph properties have not been explored as the basis for a clustering algorithm. In graph theory, a subgraph of a graph is distance-preserving if the distances (lengths of shortest paths) between every pair of vertices in the subgraph are the same as the corresponding distances in the original graph. In this paper, we consider the question of finding proper distance-preserving subgraphs, and the problem of partitioning a simple graph into an arbitrary number of distance-preserving subgraphs for clustering purposes. We also present a clustering algorithm called DP-Cluster, based on the notion of distance-preserving subgraphs. One area of research that makes considerable use of graph theory is the analysis of social networks. For this reason we evaluate the performance of DP-Cluster on two real-world social network datasets.