社区检测已成为复杂网络分析领域的一个关键问题,其本质在于将网络划分为组或社区,其中同一社区内的节点比其社区外的节点表现出更密集的连接。然而现有的标签传播方法大都稳定性不高。为此,提出一种基于节点重要性的社区检测算法,首先,根据邻居相似性计算节点重要性,然后依据节点重要性重排标签更新顺序,最后,结合节点重要性和标签更新顺序进行标签传播。实验结果表明：提出的算法具有更稳定的社团划分结果,其模块性和标准归一化指标有较好的表现,并且所提出的算法在面对稀疏的网络中表现更好。
Abstract
Community detection has become a key issue in the field of complex network analysis, which essentially involves dividing the network into groups or communities, where nodes within the same community exhibit more dense connections than nodes outside their community. However, most existing label propagation methods are not stable enough. To this end, this paper proposes a community detection algorithm based on node importance. Firstly, node importance is calculated based on neighbor similarity. Then, label update order is rearranged based on node importance. Finally, label propagation is performed by combining node importance and label update order. The experimental results show that the proposed algorithm has more stable community partitioning results, and its modularity and standard normalization indicators have good performance.
关键词
社区检测 /
复杂网络 /
节点重要性 /
标签传播
Key words
community detection /
complex network /
node importance /
label propagation
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] 赵卫绩,张凤斌,刘井莲.复杂网络社区发现研究进展[J].计算机科学,2020,47(2):10-20.
[2] M.E.Newman.Modularity and community structure in networks[J]. Proceedings of the national academy of sciences, vol.103,no.23,pp.8577-8582,2006.
[3] V.D.Blondel,J.L.Guillaume,R.Lambiotte,et al.Fast unfolding of communities in large networks[J].Journal of statistical mechanics: theory and experiment,vol.2008,no.10,p. P10008,2008.
[4] V. A. Traag,L. Waltman,and N. J.Van Eck. From louvain to leiden:guaranteeing well-connected communities[J].Scientific reports,vol. 9,no. 1,pp. 1-12,2019.
[5] M.Rosvall and C.T.Bergstrom.Maps of random walks on complex networks reveal community structure[J].Proceedings of the national academy of sciences,vol.105,no.4,pp.1118-1123,2008.
[6] B.Perozzi,R.Al-Rfou,and S.Skiena.Deepwalk:Online learning of social representations[C]//in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining,2014,pp. 701-710.
[7] A.Grover and J.Leskovec.node2vec:Scalable feature learning for networks[C]//in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining,2016,pp.855-864.
[8] U.N.Raghavan,R.Albert,and S.Kumara.Near linear time algorithm to detect community structures in large-scale networks[J].Physical review E,vol.76,no.3,p.036106,2007.
[9] J.Xie,B.K.Szymanski,and X.Liu.Slpa:Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//in 2011 ieee 11th international conference on data mining workshops.IEEE,2011,pp.344-349.
