计算机科学 ›› 2023, Vol. 50 ›› Issue (3): 155-163.doi: 10.11896/jsjkx.211200261
段顺然, 尹美娟, 刘粉林, 焦隆隆, 于岚岚
DUAN Shunran, YIN Meijuan, LIU Fenlin, JIAO Longlong, YU Lanlan
摘要: 节点影响力排序一直是复杂网络研究的热点问题。Susceptible-Infected-Recovered(SIR)模型是一种较为理想的节点影响力排序方法,业内常将其用于评价其他的节点影响力排序方法,但该方法时间复杂度较高,难以实际应用。文中提出一个基于sir值学习的节点影响力排序模型,模型综合节点的局部和全局结构信息描述节点特征,利用机器学习方法构建sir值学习模型,以构建的同等规模网络的节点特征和sir值对模型进行训练,训练后的模型能够基于节点特征预测节点的sir值,进而实现节点影响力排序。文中基于该模型实现了一个具体的节点影响力排序方法,并在真实数据集上进行了实验,结果表明,基于该模型得到的影响力排序结果,其准确性和单调性相比度中心性、Kshell、Weighted Kshell degree neighborhood等基于结构特征的方法均有所提升。
中图分类号:
[1]FANG J Q,WANG X F,ZHENG Z G,et al.A New Interdisciplinary Science: Network Science (I)[J].Progress in Physics,2007(3):239-343. [2]KEMPE D,KLEINBERG J M,TARDOS É.Maximizing theSpread of Influence through a Social Network[J].Journal of Chemical Theory and Computation,2015,11:105-147. [3]MAJI G,MANDAL S,SEN S.A systematic survey on influential spreaders identification in complex networks with a focus on K-shell based techniques[J].Expert Systems With Applications,2020,161(Dec.):113681.1-113681.18. [4]ALBERT R,JEONG H,BARABÁSI A L.Diameter of theWorld-Wide Web[J].Nature,1999,401(6749):130-131. [5]FREEMAN L C.A Set of Measures of Centrality Based on Betweenness[J].Sociometry,1977,40(1):35-41. [6]KITSAK M,GALLOS L,HAVLIN S,et al.Identification of influential spreaders in complex networks[J].Nature Physics,2010,6(11):888-893. [7]PASTOR-SATORRAS R,VESPIGNANI A.Epidemic dynamics and endemic states in complex networks[J].Physical Review E,2001,63(6):066117. [8]ZAREIE A,SHEIKHAHMADI A.A hierarchical approach for influential node ranking in complex social networks[J].Expert Systems with Applications,2018,93:200-211. [9]ZHAO J,WANG Y,DENG Y.Identifying influential nodes incomplex networks from global perspective[J].Chaos,Solitons &Fractals,2020,133(7261):109637. [10]NAMTIRTHA A,DUTTA A,DUTTA B.Weighted kshell degree neighborhood:A new method for identifying the influential spreaders from a variety of complex network connectivity structures[J].Expert Systems with Application,2020,139(Jan.):112859.1-112859.15. [11]WEI D,DENG X,ZHANG X,et al.Identifying influential nodes in weighted networks based on evidence theory[J].Physica A:Statistical Mechanics and its Applications,2013,392(10):2564-2575. [12]LIU Y,TANG M,ZHOU T,et al.Identify influential spreaders in complex networks,the role of neighborhood[J].CoRR,2015,452:289-298. [13]LÜ L Y,ZHOU T,ZHANG Q M,et al.The H-index of a network node and its relation to degree and coreness[J].Nature Communications,2016,7(1):10168. [14]SABIDUSSI G.The centrality index of a graph[J].Psy-chometrika,1966,31(4):581-603. [15]PAGE L,BRIN S,MOTWANI R,et al.The PageRank Citation Ranking:Bringing Order to the Web[R].Stanford:Stanford InfoLab,1999. [16]BORGATTI S P,EVERETT M G.Models of core/peripherystructures[J].Social Networks,2000,21(4):375-395. [17]CHAWLA P,MANGAL R,CHANDRASHEKAR C M.Dis-crete-time quantum walk algorithm for ranking nodes on a network[J].arXiv:1905.06575,2020. [18]BAE J,KIM S.Identifying and ranking influential spreaders in complex networks by neighborhood coreness[J].Physica A:Statistical Mechanics and its Applications,2014,395:549-559. [19]LUO J L,JIN J C,WANG L.Evaluation Method for Node Importance in Air Defense Networks Based on Functional Contribution Degree[J].Computer Science,2018,45(2):175-180,202. [20]ZENG A,ZHANG C J.Ranking spreaders by decomposing complex networks[J].Physics Letters A,2013,377(14):1031-1035. [21]ZAREIE A,SHEIKHAHMADI A,JALILI M,et al.Finding influential nodes in social networks based on neighborhood correlation coefficient[J].Knowledge-Based Systems,2020,194:105580. [22]ZHAO N,BAO J,CHEN N.Ranking Influential Nodes in Complex Networks with Information Entropy Method[J].Complexity,2020,2020(3):1-15. [23]MAJI G,DUTTA A,CURADO MALTA M,et al.Identifyingand ranking super spreaders in real world complex networks without influence overlap[J].Expert Systems with Applications,2021,179:115061. [24]NAMTIRTHA A,DUTTA A,DUTTA B.Identifying influential spreaders in complex networks based on kshell hybrid me-thod[J].Physica A:Statistical Mechanics and its Applications,2018,499:310-324. [25]KEELING M J,EAMES K T D.Networks and epidemic models[J].Journal of the Royal Society,Interface,2005,2(4):295-307. [26]HORNIK K,STINCHCOMBE M,WHITE H.Multilayer feedforward networks are universal approximators[J].Neural Networks,1989,2(5):359-366. [27]MA L,MA C,ZHANG H F,et al.Identifying influential spreaders in complex networks based on gravity formula[J].Physica A:Statistical Mechanics and its Applications,2016,451:205-212. [28]BARABAÁSI A L.Networks Science[M].Cambridge:Cam-bridge University Press,2016. [29]ROSSI R A,AHMED N K.The Network Data Repository with Interactive Graph Analytics and Visualization[C]//Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence.2015. [30]WEBBER W,MOFFAT A,ZOBEL J.A Similarity Measure for Indefinite Rankings[J].ACM Transactions on Information Systems,2010,28(4):1-38. |
[1] | 郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146 |
[2] | 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178 |
[3] | 杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123 |
[4] | 王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206 |
[5] | 陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177 |
[6] | 赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107 |
[7] | 潘雨, 王帅辉, 张磊, 胡谷雨, 邹军华, 王田丰, 潘志松. 复杂网络社团发现综述 Survey of Community Detection in Complex Network 计算机科学, 2022, 49(11A): 210800144-11. https://doi.org/10.11896/jsjkx.210800144 |
[8] | 原慧琳, 冯宠. 基于k-shell熵的影响力节点的排序与识别 Ranking and Recognition of Influential Nodes Based on k-shell Entropy 计算机科学, 2022, 49(11A): 210800177-5. https://doi.org/10.11896/jsjkx.210800177 |
[9] | 原慧琳, 韩真, 冯宠, 黄碧, 刘军涛. 基于核心节点影响力的社区发现方法 Community Discovery Method Based on Influence of Core Nodes 计算机科学, 2022, 49(11A): 211100002-7. https://doi.org/10.11896/jsjkx.211100002 |
[10] | 刘扬, 郑文萍, 张川, 王文剑. 一种基于局部随机游走的标签传播算法 Local Random Walk Based Label Propagation Algorithm 计算机科学, 2022, 49(10): 103-110. https://doi.org/10.11896/jsjkx.220400145 |
[11] | 李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129 |
[12] | 穆俊芳, 郑文萍, 王杰, 梁吉业. 基于重连机制的复杂网络鲁棒性分析 Robustness Analysis of Complex Network Based on Rewiring Mechanism 计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108 |
[13] | 胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉. 基于复杂网络的全球航空网络结构分析与应用 Analysis and Application of Global Aviation Network Structure Based on Complex Network 计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112 |
[14] | 王学光, 张爱新, 窦炳琳. 复杂网络上的非线性负载容量模型 Non-linear Load Capacity Model of Complex Networks 计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040 |
[15] | 马媛媛, 韩华, 瞿倩倩. 基于节点亲密度的重要性评估算法 Importance Evaluation Algorithm Based on Node Intimate Degree 计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184 |
|