基于随机游走的改进标签传播算法

doi:10.11772/j.issn.1001-9081.2020061048

计算机应用 ›› 2020, Vol. 40 ›› Issue (12): 3423-3429.DOI: 10.11772/j.issn.1001-9081.2020061048

• 2020年中国粒计算与知识发现学术会议(CGCKD 2020) • 上一篇下一篇

基于随机游走的改进标签传播算法

郑文萍^1,2, 岳香豆^1,2, 杨贵^1,2

1. 山西大学计算机与信息技术学院, 太原 030006;
2. 计算智能与中文信息处理教育部重点实验室(山西大学), 太原 030006

收稿日期:2020-06-12 修回日期:2020-09-17 出版日期:2020-12-10 发布日期:2020-11-10
通讯作者: 郑文萍(1979-),女,山西晋中人,副教授,博士,CCF会员,主要研究方向:图论算法、生物信息学。wpzheng@sxu.edu.cn
作者简介:岳香豆(1993-),女,山西运城人,硕士研究生,主要研究方向:复杂网络社区发现;杨贵(1975-),男,山西大同人,博士研究生,主要研究方向:生物信息学
基金资助:
山西省自然科学基金资助项目（201801D121123）；山西省回国留学人员科研基金资助项目（2017-014）。

Improved label propagation algorithm based on random walk

ZHENG Wenping^1,2, YUE Xiangdou^1,2, YANG Gui^1,2

1. School of Computer and Information Technology, Shanxi University, Taiyuan Shanxi 030006, China;
2. Key Laboratory of Computational Intelligence and Chinese Information Processing, Ministry of Education(Shanxi University), Taiyuan Shanxi 030006, China

Received:2020-06-12 Revised:2020-09-17 Online:2020-12-10 Published:2020-11-10
Supported by:
This work is partially supported by the Natural Science Foundation of Shanxi Province （201801D121123）， the Research Project of the Shanxi Scholarship Council of China （2017-014）.

摘要/Abstract

摘要： 社区发现是挖掘社交网络隐藏信息的一个有用的工具，而标签传播算法（LPA）是社区发现算法中的一种常见算法，不需要任何的先验知识，且运行速度快。针对标签传播算法有很强的随机性而导致的社区发现算法结果不稳定的问题，提出了一种基于随机游走的改进标签传播算法（LPARW）。首先，根据在网络上进行随机游走确定了节点重要性的排序，从而得到节点的更新顺序；然后，遍历节点的更新序列，对每个节点将其与排序在其之前的节点进行相似性计算，若该节点与排序在其之前的节点是邻居节点且它们之间的相似性大于阈值，则将排序在其之前的节点选为种子节点；最后，将种子节点的标签传播给其余的节点，得到社区的最终划分结果。将所提算法与一些经典的标签传播算法在4个有标签的网络和5个无标签的真实网络上进行比较分析，实验结果表明所提算法在标准互信息（NMI）、调整兰德系数（ARI）和模块度等经典的评价指标上的性能均优于其余对比算法，可见该算法具有很好的社区划分效果。

关键词: 复杂网络, 社区发现, 标签传播算法, 随机游走, 种子扩展策略

Abstract: Community detection is a useful tool for mining hidden information in social networks. And Label Propagation Algorithm (LPA) is a common algorithm in the community detection algorithm, which does not require any prior knowledge and runs fast. Aiming at the problem of the instability of community detection algorithm results caused by the strong randomness of label propagation algorithm, an improved Label Propagation Algorithm based on Random Walk (LPARW) was proposed. Firstly, according to the random walk on the network, the importance order of nodes was determined, so as to obtain the update order of nodes. Secondly, the update sequence of nodes was traversed, and the similarity calculation between each node and the node before it was performed. If the node and the node before it were neighbor nodes and the similarity between them was greater than the threshold, then the node before it was selected as the seed node. Finally, the label of the seed node was propagated to the rest of the nodes in order to obtain the final division result of the communities. The proposed algorithm was comparatively analyzed with some classic label propagation algorithms on 4 labeled networks and 5 unlabeled real networks. Experimental results show that the proposed algorithm is better than other comparison algorithms on classic evaluation indicators such as Normalized Mutual Information (NMI), Adjusted Rand Index (ARI) and modularity. It can be seen that the proposed algorithm has the good community division effect.

Key words: complex network, community detection, Label Propagation Algorithm (LPA), random walk, seed expansion strategy

中图分类号:

TP391.1

郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.

ZHENG Wenping, YUE Xiangdou, YANG Gui. Improved label propagation algorithm based on random walk[J]. Journal of Computer Applications, 2020, 40(12): 3423-3429.

参考文献

[1] KIM J,HASTAK M. Socialnetwork analysis:characteristics of online socialnetworks after a disaster[J]. International Journal of Information Management,2018,38(1):86-96.
[2] NEWMAN M E J. Networks:An Introduction[M]. Oxford:Oxford University Press,2010:218-221.
[3] YILMAZ L S,WALHOUT A J M. Metabolicnetwork modeling with modelorganisms[J]. Current Opinion in Chemical Biology,2017, 36:32-39.
[4] CHOI J M,GILSON A I,SHAKHNOVICH E I. Graph's topology and free energy of a spin model on the graph[J]. Physical Review Letters,2017,118(8):Article No. 088302.
[5] MARTINEZ-LEDESMA E,VERHAAK R G W,TREVIÑO V. Identification of a multi-cancer gene expression biomarker for cancer clinical outcomes using anetwork-based algorithm[J]. Scientific Reports,2015,5:Article No. 11966.
[6] WASSERMAN S,FAUST K. Social Network Analysis:Methods and Applications[M]. Cambridge:Cambridge University Press, 1994:67-89.
[7] LANCICHINETTI A, FORTUNATO S. Community detection algorithms:acomparative analysis[J]. Physical Review E:Statistical,Nonlinear,and Soft Matter Physics,2009,80(5 Pt 2):Article No. 056117.
[8] 刘大有, 金弟, 何东晓, 等. 复杂网络社区挖掘综述[J]. 计算机应用与发展, 2013, 50(10):2140-2154.(LIU D Y,JIN D,HE D X, et al. Community mining incomplexnetworks[J]. Journal of Computer Research and Development, 2013, 50(10):2140-2154.)
[9] NEWMAN M E J. Spectral methods forcommunity detection and graph partitioning[J]. Physical Review E:Statistical,Nonlinear, and Soft Matter Physics,2013,88(4):Article No. 042822.
[10] GIRVAN M,NEWMAN M E J. Community structure in social and biologicalnetworks[J]. Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[11] NEWMAN M E J. Fast algorithm for detectingcommunity structure innetworks[J]. Physical Review E:Statistical, Nonlinear,and Soft Matter Physics,2004,69(6 Pt 2):Article No. 066133.
[12] BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al. Fast unfolding ofcommunities in largenetworks[J]. Journal of Statistical Mechanics:Theory and Experiment,2008(10):Article No. P10008.
[13] PALLA G,DERÉNYI I,FARKAS I,et al. Uncovering the overlappingcommunity structure ofcomplexnetworks in nature and society[J]. Nature,2005,435(7043):814-818
[14] RAGHAVAN U N,ALBERT R,KUMARA S. Near linear time algorithm to detectcommunity structure in large-scalenetwork[J]. Physical Review E:Statistical,Nonlinear,and Soft Matter Physics,2007,76(3 Pt 2):Article No. 036106.
[15] GREGORY S. An algorithm to find overlappingcommunity structure innetworks[C]//Proceedings of the 2007 European Conference on Principles of Data Mining and Knowledge Discovery,LNCS 4702. Berlin:Springer,2007:91-102
[16] XIE J,SZYMANSKI B K,LIU X. SLPA:uncovering overlappingcommunities in socialnetworks via a speaker-listener interaction dynamic process[C]//Proceedings of the 2011 IEEE 11th International Conference on Data Mining Workshops. Piscataway:IEEE,2011:344-349.
[17] BARBER M J,CLARK J W. Detectingnetworkcommunities by propagating labels under constraints[J]. Physical Review E:Statistical,Nonlinear,and Soft Matter Physics,2009,80(2 Pt 2):Article No. 026129.
[18] LIU X, MURATA T. Advanced modularity-specialized label propagation algorithm for detectingcommunities innetworks[J]. Physica A:Statistical Mechanics and its Applications,2010,389(7):1493-1500.
[19] LI W, HUANG C, WANG M, et a1. Steppingcommunity detection algorithm based on label propagation and similarity[J]. Physica A:Statistical Mechanics and its Applications,2017, 472:145-155.
[20] 郑文萍, 车晨浩, 钱宇华, 等. 一种基于标签传播的两阶段社区发现算法[J]. 计算机研究与发展, 2018, 55(9):1959-1971. (ZHENG W P,CHE C H,QIAN Y H,et al. A two-stagecommunity detection algorithm based on label propagation[J]. Journal of Computer Research and Development,2018,55(9):1959-1971.)
[21] 宋琛, 张贤坤, 费松, 等. 基于随机游走相似度矩阵的改进标签传播算法[J]. 计算机应用与软件, 2016, 33(8):269-272. (SONG C,ZHANG X K,FEI S,et al. An improved label propagation algorithm based on random walk similarity matrix[J]. Journal of Computer Applications and Software,2016,33(8):269-272.)
[22] EVANS T S,LAMBIOTTE R. Line graphs,link partitions,and overlappingcommunities[J]. Physical Review E:Statistical, Nonlinear,and Soft Matter Physics,2009,80(1 Pt 2):Article No. 016105.
[23] 王杰, 梁吉业, 郑文萍. 一种面向蛋白质复合体检测的图聚类方法[J]. 计算机研究与发展, 2015, 52(8):1784-1973.(WANG J, LIANG J Y, ZHENG W P. A graph clustering method for detecting proteincomplexes[J]. Journal of Computer Research and Development,2015,52(8):1784-1973.)
[24] WANG J,ZHENG W,QIAN Y,et al. A seed expansion graph clustering method for proteincomplexes detection in protein interactionnetworks[J]. Molecules,2017,22(12):2179.
[25] 汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京:高等教育出版社, 2012:119-152.(WANG X F,LI X,CHEN G R. Network Science:an Introduction[M]. Beijing:Higher Education Press, 2012:119-152.)
[26] LUSSEAU D,NEWMAN M E J. Identifying the role that animals play in their socialnetworks[J]. Proceedings of the Royal Society of B:Biological Sciences,2004,271(S6):S477-S481.
[27] 郑文萍, 车晨浩, 钱宇华, 等. 一种基于节点间路径度量的图聚类算法[J]. 计算机学报, 2020, 43(7):1312-1327.(ZHENG W P,CHE C H,QIAN Y H,et al. A graph clustering algorithm based on local paths between nodes incomplexnetworks[J]. Chinese Journal of Computers,2020,43(7):1312-1327.)
[28] GIRVAN M,NEWMAN M E J. Community structure in social and biologicalnetworks[J]. Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.

基于随机游走的改进标签传播算法

Improved label propagation algorithm based on random walk

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	蔡彪, 李蕊岑, 吴媛媛. 相似性特征对链路预测的影响与增强[J]. 计算机应用, 2021, 41(9): 2569-2577.
[2]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[3]	余敦辉, 张蕗怡, 张笑笑, 毛亮. 基于知识图谱和重启随机游走的跨平台用户推荐方法[J]. 计算机应用, 2021, 41(7): 1871-1877.
[4]	李亚芳, 梁烨, 冯韦玮, 祖宝开, 康玉健. 基于社区优化的深度网络嵌入方法[J]. 计算机应用, 2021, 41(7): 1956-1963.
[5]	秦丽, 郝志刚, 李国亮. 国家食品安全标准图谱的构建及关联性分析[J]. 计算机应用, 2021, 41(4): 1005-1011.
[6]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[7]	罗香玉, 李嘉楠, 罗晓霞, 王佳. 改进的动态图社区演化关系分析方法[J]. 计算机应用, 2020, 40(8): 2313-2318.
[8]	杜旭升, 于炯, 叶乐乐, 陈嘉颖. 基于图上随机游走的离群点检测算法[J]. 计算机应用, 2020, 40(5): 1322-1328.
[9]	郭景峰, 董慧, 张庭玮, 陈晓. 主题关注网络的表示学习[J]. 计算机应用, 2020, 40(2): 441-447.
[10]	李莎莎, 梁冬阳, 余杰, 纪斌, 马俊, 谭郁松, 吴庆波. 基于师门关系的研究团队挖掘算法[J]. 计算机应用, 2020, 40(11): 3198-3202.
[11]	成其伟, 陈启买, 贺超波, 刘海. 基于改进对称二值非负矩阵分解的重叠社区发现方法[J]. 计算机应用, 2020, 40(11): 3203-3210.
[12]	刘昱阳, 李龙杰, 单娜, 陈晓云. 融合聚集系数的链接预测方法[J]. 计算机应用, 2020, 40(1): 28-35.
[13]	王西龙, 王继成, 罗成, 田秀霞. 时间尺度与选择倾向性协同作用下的演化博弈模型[J]. 计算机应用, 2019, 39(6): 1824-1828.
[14]	张琪, 纪淑娟, 傅强, 张纯金. 基于带权评论图的水军群组检测及特征分析[J]. 计算机应用, 2019, 39(6): 1595-1600.
[15]	张希, 朱利, 刘路辉, 詹杭龙, 卢艳民. 基于多层网络的银行间市场信用拆借智能风险传染机制[J]. 计算机应用, 2019, 39(5): 1507-1511.