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

doi:10.3969/j.issn.1000-3428.2017.11.029

计算机工程

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

杨晓波¹,陈楚湘 ¹,王至婉²

(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¹,CHEN Chuxiang¹,WANG Zhiwan²

(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

摘要/Abstract

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

杨晓波，陈楚湘，王至婉. 基于随机游走理论的改进LFM算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2017.11.029.

YANG Xiaobo,CHEN Chuxiang,WANG Zhiwan. Improved LFM Algorithm Based on Random Walk Theory [J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2017.11.029.

参考文献

参考文献［1］韩忠明,谭旭升,陈炎,等.NCSS:一种快速有效的复杂网络社团划分算法［J］.中国科学:信息科学,2016,46(4):431-444. ［2］GIRVAN M,NEWMAN M E J.Community Structure in Social and Biological Networks［J］.Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826. ［3］NEWMANM E J.Fast Algorithm for Detecting Community Structure in Networks［J］.Physica A Statistical Mechanics & Its Applications,2007,384(2):667-674. ［4］NEWMANM E J.First-principles Multiway Spectral Partitioning of Graphs［J］.Journal of Complex Networks,2014,2(2):121-140. ［5］RAGHAVANU N,ALBERT R,KUMARA S.Near Linear Time Algorithm to Detect Community Structures in Large-scale Networks［J］.Physical Review E:Statistical Nonlinear & Soft Matter Physics,2007,76(3):036106. ［6］BLONDELV D,GUILLAUME J L,LAMBIOTTE R,et al.Fast Unfolding of Communities in Large Networks［J］.Journal of Statistical Mechanics,2008,30:155-168. ［7］刘大有,金弟,何东晓,等.复杂网络社区挖掘综述［J］.计算机研究与发展,2013,50(10):2140-2154. ［8］PONS P,LATAPY M.Computing Communities in Large Networks Using Random Walks［C］//Proceedings of International Symposium on Computer and Information Sciences.Berlin,Germany:Springer,2006:191-218. ［9］CLAUSET A.Finding Local Community Structure in Networks［J］.Physical Review E:Statistical Nonlinear & Soft Matter Physics,2005,72(2):26132. ［10］LANCICHINETTI A,FORTUNATO S.Detecting the Overlapping and Hierarchical Community Structure in Complex Networks［J］.New Journal of Physics,2009,11(3):19-44. ［11］金杰.基于关系强度的复杂网络社团结构分析方法研究［D］.南京:南京大学,2013. ［12］袁超,柴毅.复杂网络的局部社团结构挖掘算法［J］.自动化学报,2014,40(5):921-934. ［13］刘栋.复杂网络社区发现方法以及在网络扰动中的影响［D］.天津:天津大学,2013. ［14］PONS P,LATAPY M.Computing Communities in Large Networks Using Random Walks［J］.Journal of Graph Algorithms and Applications,2006,10(2):191-218. ［15］程建军.复杂网络中的社团检测方法研究［D］.兰州:兰州大学,2015. ［16］LIU W P,L L Y.Link Prediction Based on Local Random Walk［J］.Euro Physics Letters,2010,89(5):1-7. ［17］LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark Graphs for Testing Community Detection Algorithms［J］.Physical Review E,2008,78(2):561-570. ［18］LANCICHINETTI A,FORTUNATO S.Community Detection Algorithms:A Comparative Analysis［J］.Physical Review E,2009,80(2):2142-2152. 编辑陆燕菲

[1]	李英乐, 何赞园, 王凯, 许明艳. 基于资源传输节点拓扑紧密性的链路预测方法[J]. 计算机工程, 2021, 47(1): 50-57.
[2]	汤伟韬, 余敦辉, 魏世伟. 融合知识图谱与用户评论的商品推荐算法[J]. 计算机工程, 2020, 46(8): 93-100.
[3]	张志敏, 柴变芳, 李文斌. 基于稀疏自编码器的属性网络嵌入算法[J]. 计算机工程, 2020, 46(7): 98-103,109.
[4]	马慧芳, 李苗, 童海斌, 詹子俊. 基于通配符模式与随机游走的关键词提取方法[J]. 计算机工程, 2020, 46(7): 78-83.
[5]	邱少明, 於涛, 杜秀丽, 陈波. 基于节点多属性相似性聚类的社团划分算法[J]. 计算机工程, 2020, 46(7): 84-90,97.
[6]	王曙燕, 韩雪, 孙家泽. 基于风险轨迹与复杂网络的缺陷定位方法[J]. 计算机工程, 2020, 46(6): 202-208.
[7]	谢菁, 羿舒文, 张毅. 基于双曲空间嵌入的极小值社区划分算法[J]. 计算机工程, 2020, 46(6): 73-80.
[8]	吴涛, 任淑霞, 张书博. 基于三角形子图的复杂网络过滤压缩算法[J]. 计算机工程, 2020, 46(5): 70-77.
[9]	朱江, 包崇明, 王崇云, 周丽华, 孔兵. 基于图结构特征分析的Top-k结构洞发现算法[J]. 计算机工程, 2020, 46(5): 94-101,108.
[10]	孟磊, 冶忠林, 赵海兴, 杨燕琳. 超网络模型构建中优先连接方法研究[J]. 计算机工程, 2020, 46(10): 103-111.
[11]	符汉杰, 熊赟, 朱扬勇. TLP:一个动态网络中的时序链路预测算法[J]. 计算机工程, 2020, 46(1): 67-73.
[12]	陆圣宇, 欧锋, 黄清元, 刘宝, 路振民, 汤凌韬. 基于资源分配与偏好连接的局部路径链路预测算法[J]. 计算机工程, 2019, 45(9): 316-320.
[13]	高秀娥, 陈小双, 王运明, 陈波. 基于桥接系数的指挥控制网络桥边识别方法[J]. 计算机工程, 2019, 45(7): 309-314.
[14]	王思檬,曹佳. 边异质网络中的社区结构发现算法[J]. 计算机工程, 2019, 45(6): 140-145.
[15]	丁明珠,马英红,李云. 基于相似度指标的社团划分算法[J]. 计算机工程, 2019, 45(2): 195-201.

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

Improved LFM Algorithm Based on Random Walk Theory

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10