基于复杂网络的社区发现算法研究

近年来,高质量社区的挖掘和发现已经成为复杂网络研究的一个热点。目前大多的社区发现算法主要针对无向网络,但现在的很多真实网络通常都是有向加权的。同时,标签传播算法(LPA)是一种接近线性复杂度的社区发现算法,该算法具有简单高效、不需要提供社区规模和社区个数等先验知识的特点,因而得到了广泛关注和应用。针对有向加权网络,提出了一种基于节点重要性和节点相似性的改进标签传播算法(CRJ-LPA)。该算法综合考虑节点的边权、节点的信息传播能力、节点相似度以及节点集聚系数等因素。算法通过加权的ClusterRank获得节点重要性列表用以避免LPA中的随机选择;然后,采用Jaccard系数度量节点的相似度,结合节点重要性列表计算出一个新的度量CRJ(重要度和相似度),提高了算法的稳定性。实验结果表明,该算法有效可行,且具有较好的鲁棒性。

Research on Community Detection Algorithm Based on Complex Network

In recent years,the mining and discovery of high-quality communities has become a hot topic in complex network research.However,most community discovery algorithms are mainly directed at undirected networks,but many real networks are usually directed weighted.At the same time,the label propagation algorithm(LPA)is a community discovery algorithm close to linear complexity.It is simple and efficient,and does not need to provide prior knowledge such as community size and community number,which has been widely concerned and applied.For the directed weighted network,a label propagation algorithm(CRJ-LPA)based on node similarity and node importance is proposed.The node importance list is obtained by weighted ClusterRank to avoid random selection in LPA.Then,the Jaccard coefficient is used to measure the similarity of the nodes.Combined with the node importance list,a new metric CRJ(importance and similarity)is calculated to improve the stability of the algorithm.Experiment shows that the proposed algorithm is feasible and effective with strong robustness.