摘要： 传统LFM社团发现算法基于网络局部信息进行社团划分,未充分利用网络中包含的结构信息,导致社团结构模糊的网络中社团划分精度下降严重,同时算法基于局部信息扩张社团,容易形成畸形社团结构。为解决上述问题,提出一种改进的LFM算法,利用随机游走理论衡量节点相似度,使社团结构更清晰,同时寻找赋权网络中的极大子团,以子团为基本单位进行社团扩张,解决畸形社团问题。在人工网络和真实网络上的实验结果表明,与传统LFM算法、标签传播算法等相比,改进的LFM算法具有更高的社团划分精度。

关键词: 复杂网络, 社团发现, LFM算法, 随机游走, 极大子团

Abstract: Traditional LFM community discovery algorithm based on local information of network to realize community detection.However,the structure information in the whole network is underused.It leads to serious decline of algorithm precision in network with fuzzing community structure.What’s more,because of community expansion by local information,it’s easy for LFM to get abnormal community division.In order to solve the above problem,an improved LFM algorithm is proposed.Random walk theory is used to measure the similarity of nodes,so that the community structure is clearer.Meanwhile,in order to avoid abnormal community division,maximal clique in the weighted network is found and used to expand the community.The experimental results on artificial networks and real networks show that the improved LFM algorithm achieves higher classification accuracy than traditional LFM algorithm and Label Propagation Algorithm(LPA).

Key words: complex network, community detection, LFM algorithm, random walk, maximal clique

中图分类号: 

• TP391