基于节点影响力的理性节点标签传播算法

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (04): 713-722.

基于节点影响力的理性节点标签传播算法

皇甫斐斐1，杨阳2，邓晓懿2,3

(1.华侨大学外国语学院,福建泉州 362021；2.华侨大学现代应用统计与大数据研究中心,福建厦门 361021；
3.新泽西州立罗格斯大学罗格斯商学院,新泽西纽瓦克 07102)

收稿日期:2020-08-26 修回日期:2021-01-25 接受日期:2022-04-25 出版日期:2022-04-25 发布日期:2022-04-20
基金资助:
国家自然科学基金(71401058)；福建省自然科学基金(2020J01077);福建省社会科学规划项目(FJ2020B047)

A rational label propagation algorithm based on node influence

HUANGFU Fei-fei1,YANG Yang2,DENG Xiao-yi2,3

(1.College of Foreign Languages,Huaqiao University,Quanzhou 362021,China;
2.Research Center for Modern Applied Statistics & Big Data,Huaqiao University,Xiamen 361021,China;
3.Rutgers Business School,Rutgers,the State University of New Jersey,Newark,New Jersey 07102,USA)

Received:2020-08-26 Revised:2021-01-25 Accepted:2022-04-25 Online:2022-04-25 Published:2022-04-20

摘要/Abstract

摘要： 社区发现能够揭示真实社会网络的拓扑结构和重要节点。由于具有线性时间复杂度，无需定义目标函数及目标参数，标签传播算法(LPA)作为经典社区发现算法被广泛应用在学术和实践领域。针对LPA算法更新顺序的无序性和标签选择的随机性,提出基于节点影响力的理性节点标签传播算法(RLPBNI)。将节点影响力排序作为更新顺序，引入理性节点概念进行标签选择，并定义重叠度进行社区再降维。实验结果表明，与其他对比算法相比,RLPBNI算法不但可有效提高社区划分精度，且更容易发现混合程度较高的网络中隐藏的社区。

关键词: 社区发现；标签传播, 节点影响力；理性节点；复杂网络

Abstract: Community discovery can reveal the topology and important nodes of real social networks. Due to its linear time complexity and no need to define objective functions and objective parameters, Label Propagation Algorithm (LPA) is widely used in academic and practical fields as a classic community discovery algorithm. Aiming at the update disorder of LPA algorithm and the randomness of label selection, a Rational Node Label Propagation Algorithm Based on Node Influence (RLPBNI) is proposed. The algorithm takes the node influence ranking as the update order, introduces the concept of rational nodes for label selection, and defines the overlap degree for community dimensionality reduction. The analysis of the experimental results shows that, compared with other comparative algorithms, the RLPBNI algorithm can not only effectively improve the accuracy of community division, but also more easily discover hidden communities in networks with a high degree of mixing.

Key words: community detection, label propagation, node influence, rational node, complex network

皇甫斐斐, 杨阳, 邓晓懿, . 基于节点影响力的理性节点标签传播算法[J]. 计算机工程与科学, 2022, 44(04): 713-722.

HUANGFU Fei-fei, YANG Yang, DENG Xiao-yi, . A rational label propagation algorithm based on node influence[J]. Computer Engineering & Science, 2022, 44(04): 713-722.

参考文献［19］

［1］	Rossetti G,Cazabet R.Community discovery in dynamic networks:A survey［J］.ACM Computing Surveys,2018,51(2):35.
［2］	Newman M E J. Fast algorithm for detecting community structure in networks［J］.Physical Review E,2004,69(6):066133.
［3］	Newman M E J.Modularity and community structure in networks［J］.Proceedings of the National Academy of Sciences,2006,103(23):8577-8582.
［4］	Blondel V D,Guillaume J L,Lambiotte R,et al.Fast unfold- ing of communities in large networks［J］.Journal of Statistical Mechanics Theory & Experiment,2008(10):155-168.
［5］	Cao J,Bu Z,Gao G,et al.Weighted modularity optimization for crisp and fuzzy community detection in large-scale networks［J］.Physica A:Statistical Mechanics and its Applications,2016,462:386-395.
［6］	Liu Yao,Kang Xiao-hui,Gao Hong,et al.A community detecting method based on the node intimacy and degree in social network ［J］.Journal of Computer Research and Development,2015,52(10):2363-2372.(in Chinese)
［7］	Yang L,Cao X,He D,et al.Modularity based community detection with deep learning［C］∥Proc of the 25th International Joint Conference on Artificial Intelligence,2016:2252-2258.
［8］	Cavallari S,Zheng V W,Cai H,et al.Learning community embedding with community detection and node embedding on graphs［C］∥Proc of the 2017 ACM Conference on Information and Knowledge Management,2017:377-386.
［9］	Wang Hong-jie,Teng Fei,Li Tian-rui.Incremental learning algorithm of community detection under guidance of modularity ［J］.Journal of Frontiers of Computer Science and Technology,2017,11(4):556-564.(in Chinese)
［10］	Raghavan U N,Albert R,Kumara S.Near linear time algorithm to detect community structures in large-scale networks［J］.Physical Review E,2007,76(3):036106.
［11］	Leung I X,Hui P,Lio P,et al.Towards real-time community detection in large networks［J］.Physical Review E,2009,79(6):066107.
［12］	Barber M J,Clark J W.Detecting network communities by propagating labels under constraints［J］.Physical Review E,2009,80(2):026129.
［13］	Liu X, Murata T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks［J］.Physica A:Statistical Mechanics and its Applications,2009,389(7):1493-1500.
［14］	Li W,Huang C,Wang M,et al.Stepping community detection algorithm based on label propagation and similarity［J］.Physica A:Statistical Mechanics and its Applications,2017,472:145-155.
［15］	He M,Leng M,Li F,et al.A node importance based label propagation approach for community detection［M］∥Knowledge Engineering and Management.Berlin:Springer Berlin Heidelberg,2014.
［16］	Xing Y,Meng F,Zhou Y,et al.A node influence based label propagation algorithm for community detection in networks［J］.The Scientific World Journal,2014(5):627581.
［17］	Sun H,Liu J,Huang J,et al.CenLP:A centrality-based label propagation algorithm for community detection in networks［J］.Physica A:Statistical Mechanics and its Applications,2015,436:767-780.
［18］	Lü L,Chen D,Ren X L,et al.Vital nodes identification in complex networks［J］.Physics Reports,2016,650:1-63.
［19］	Deng Xiao-yi,Yang Yang,Jin Chun.Identifying influential nodes based on network topology［J］.Operations Research and Management Science,2019,28(7):91-99.(in Chinese)
［20］	Leskovec J,Mcauley J J.Learning to discover social circles in ego networks［C］∥Proc of the 25th International Confe- rence on Neural Information Processing Systems,2012:539-547.
［21］	Lancichinetti A,Fortunato S.Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities［J］.Physical Review E,2009,80(1):016118.
［22］	Peng G S.Weighting links based on edge centrality for community detection［J］.Physica A:Statistical Mechanics and its Applications,2014,394:346-357.
［23］	Santos J M,Embrechts M.On the use of the adjusted rand index as a metric for evaluating supervised classification［C］∥Proc of International Conference on Artificial Neural Networks,2009:175-184.
	附中文参考文献：
［6］	刘瑶，康晓慧，高红，等.基于节点亲密度和度的社会网络社团发现方法［J］.计算机研究与发展,2015,52(10)：2363-2372.
［9］	王宏杰，滕飞，李天瑞.模块度引导下的社区发现增量学习算法［J］.计算机科学与探索,2017,11(4)：556-564.
［19］	邓晓懿，杨阳，金淳.基于网络拓扑结构的重要节点发现算法［J］.运筹与管理,2019,28(7)：91-99.