一种基于结构相似性的图聚类算法

图聚类是发现网络中潜在结构的一项重要任务。提出一种基于结构相似性的图聚类算法GNSCAN，给出该算法的相关定义以及算法的执行过程。采用真实数据集对该算法进行测试，从理论分析及结果2方面证明GNSCAN算法在效率上比GN算法得到明显的提高。在GNSCAN算法的基础上，提出一种改进的GNSCAN算法IGNSCAN，算法时间复杂度得到进一步降低。

A Graph Clustering Algorithm Based on Structural Similarity

Network clustering (or graph partitioning) is an important task for the discovery of underlying structures in networks. In this paper, a fast algorithm named GNSCAN based on structure similarity is proposed, and the related definition and algorithm implementation process are given. In order to test the performance of the algorithm, a group of real datasets are used to test the algorithm. The theoretical analysis and experimental results show that the proposed GNSCAN algorithm is improved in efficiency. On the basis of the above GNSCAN algorithm, IGNSCAN is proposed. And the computation complexity of the algorithm IGNSCAN is more efficiency.