基于随机游走的级联网络社区发现算法

Community detection in cascade networks using random walks

随着Web 2.0的不断推广以及社交应用的不断普及,在线社交网络结构分析得到了各领域学者的广泛关注。社区是网络中内嵌的密集群组,保证了社区内部用户的强相关性和一致性,因此广泛应用于病毒防护、商品推荐等现实系统。本文提出一种基于随机游走的级联网络社区发现算法,主要解决非直连节点间的相似性度量问题。提出一种基于2-hop随机游走的局部可达性计算方法,通过对游走终点一致的节点进行层次聚类,社区结构可在较短的时间内迭代生成。实验结果表明,本方法在级联网络社区发现中具有较高的性能和效率,对星形社区具有较高的匹配性。

With the continuous promotion of Web 2.0 and the continuous popularization of social applications,the structural analysis of online social networks has attracted extensive attention from scholars in various fields.Community is a dense group embedded in the network,which ensures the strong correlation and consistency of users within the community.Therefore,it is widely used in virus protection,commodity recommendation,and other practical systems.In this paper,a cascade network community discovery algorithm based on the random walk is proposed to solve the similarity measurement problem of non-directly connected nodes.The paper proposes a local reachability calculation method based on 2-hop random walks.The community structure can be generated iteratively in a short time by hierarchical clustering of nodes with consistent endpoints.The experimental results show that this method has high performance and efficiency in cascaded network community detection and has a high matching to the star community.