计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

基于随机游走理论的改进LFM算法

杨晓波 1,陈楚湘 1,王至婉 2   

  1. (1.信息工程大学 理学院,郑州 450000; 2.河南中医大学第一附属医院 呼吸科,郑州 450000)
  • 收稿日期:2016-11-04 出版日期:2017-11-15 发布日期:2017-11-15
  • 作者简介:杨晓波(1991—),男,硕士研究生,主研方向为复杂网络、社团发现;陈楚湘,副教授、博士;王至婉,教授、博士。
  • 基金项目:
    国家自然科学基金(81574100)。

Improved LFM Algorithm Based on Random Walk Theory

YANG Xiaobo 1,CHEN Chuxiang 1,WANG Zhiwan 2   

  1. (1.College of Science,Information Engineering University,Zhengzhou 450000,China;2.Respiratory Department,the First Affiliated Hospital of Henan University of Traditional Chinese Medicine,Zhengzhou 450000,China)
  • Received:2016-11-04 Online:2017-11-15 Published:2017-11-15

摘要: 传统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

中图分类号: