图聚类的算法及其在社会关系网络中的应用

摘要

In this paper,we study the graph clustering algorithm. In partition-based graph clustering algorithm,we particularly evaluate two different distance measures between vertices and their influence to clustering result. As the vertices in social network graphics do not have coordinates,traditional distance measures like Euclidean distance or Manhattan distance cannot be used. In this paper, we use two different distance measures based on shortest path distance and random walk distance respectively when applying the k-medoids clustering algorithm, assort the social network graphics composed of DBLP dataset into various sub-graphics,and attest the advantage and disadvantage of these two algorithms with experimental data. Experiment results demonstrate that the shortest path distance has better clustering results and achieves acceptable classification effect.%研究图聚类的算法问题.在基于划分的图聚类中,重点比较点与点之间距离的计算方法及其对聚类结果的影响.由于社会关系网络图中点没有坐标值,所以不能使用欧几里得距离和曼哈坦距离.使用k-medoids聚类算法时,分别采用最短距离和随机漫步距离算法,将DBLP数据集构成的社会关系网络图分类成各个子图,通过实验数据验证两种算法的优劣.实验证明最短距离算法获得聚类效果更为理想,达到了较好的分类效果.