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

Improved label propagation algorithm based on random walk

作　　者：郑文萍[1,2] 岳香豆 杨贵[1,2] ZHENG Wenping;YUE Xiangdou;YANG Gui(School of Computer and Information Technology,Shanxi University,Taiyuan Shanxi 030006,China;Key Laboratory of Computational Intelligence and Chinese Information Processing,Ministry of Education(Shanxi University),Taiyuan Shanxi 030006,China)

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

出　　处：《计算机应用》2020年第12期3423-3429,共7页journal of Computer Applications

基　　金：山西省自然科学基金资助项目(201801D121123);山西省回国留学人员科研基金资助项目(2017-014)。

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

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

分 类 号：TP391.1[自动化与计算机技术—计算机应用技术]