基于SimRank全局矩阵平滑收敛的网络社区发现

Hierarchical Community Detection Based on Global Smooth Convergence Using SimRank

SimRank方法是一种基于图的拓扑结构信息来衡量任意两个对象间相似程度的方法,针对在真实的大规模社交网络中节点与节点之间的迭代计算过程需要消耗大量的时间,提出了一种基于SimRank全局矩阵平滑收敛的网络社区发现方法(SimRank global smooth convergence,SGSC)。首先,该算法通过经典度量来识别网络中的初始核心节点;然后利用矩阵平滑收敛来计算SimRank得到最终核心节点;最后,基于全局收敛矩阵,将社区聚集在核心节点周围,使用Closeness指数合并两个社区,通过递归的重复该过程,聚类出最终社区。在3种真实的不同规模的社交网络中将SGSC和其他2种具有代表性的方法进行比较,并验证了提出的算法在不同规模的社交网络中社区划分的准确率和算法运行的时间性能上有所提升。

SimRank is a method based on the topological structure information of the graph to measure the similarity between any two objects.However,in real large-scale social networks,the iterative computation between nodes is time-consuming.Here we propose a hierarchical community detection algorithm based on global matrix smooth convergence using SimRank,called SGSC.First,the SGSC algorithm identifies the initial core nodes in a network by classical measurement.Then,it smoothly converges a matrix to calculate SimRank to obtain original core nodes.Based on the global convergence matrix,we cluster the communities around the core nodes and use a closeness index to merge two communities.By recursively repeating the process,a dendrogram of the communities is eventually constructed.We validate the performance of SGSC by comparing its results with those of two representative methods for three real-world networks with different scales,and comparison results show that the proposed SGSC algorithm improves the accuracy in community division and reduces running time in social networks of different scales.