计算机科学 ›› 2022, Vol. 49 ›› Issue (11A): 210800177-5.doi: 10.11896/jsjkx.210800177
原慧琳1, 冯宠2
YUAN Hui-lin1, FENG Chong2
摘要: 节点的影响力排序一直是复杂网络领域中最具有吸引力的一个问题,其对于衡量节点的传播能力有着重要的作用。由于网络中的节点的规模很大,研究者们希望能够更准确地估计节点的传播能力。文中基于信息论的基本概念和k-shell方法提出了一种新的影响力节点的排序方法,根据节点所在网络中的位置的拓扑信息来测量节点的传播能力。实验结果表明,该方法可以有效地识别网络中有影响力的节点,并且可以有效避免 k-shell法的“富人俱乐部现象”。
中图分类号:
[1]ZHAO Y,LI S,JIN F.Identification of influential nodes in social networks with community structure based on label propagation [J].Neurocomputing,2016,210:34-44. [2]FREEMAN L C.Centrality in social networks conceptual clarification [J].Social Networks,1978,1(3):215-239. [3]SABIDUSSI G.The centrality index of a graph[J].Psy-chometrika,1966,31(4):581-603. [4]FREEMAN L C.A Set of Measures of Centrality Based on Betweenness[J].Sociometry,1977,40(1):35-41. [5]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(4):549-559. [6]WANG J,HOU X,LI K.A novel weight neighborhood centra-lity algorithm for identifying influential spreaders in complex networks[J].Physica A:Statistical Mechanics and its Applications,2017,475:88-105. [7]HAJARATHAIAH K,ENDURI M K,ANAMALAMUDI S.Efficient algorithm for finding the influential nodes using local relative change of average shortest path[J].Physica A:Statistical Mechanics and Its Applications,2022,591:126708. [8]LIU J G,WANG Z Y,GUO Q.Identifying multiple influential spreaders via local structural similarity[J].Europhysics Letters,2017,119(1):18001. [9]KITSAK M,GALLOS L K,HAVLIN S.Identification of influen-tial spreaders in complex networks[J].Nature Physics,2010,6(11):888-893. [10]REN Z M,LIU J G L,SHAO F.Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks[J].Acta Physica Sinica,2013,62(10):956-959. [11]HU Z L,LIU J G,YANG G Y.Effects of the distance among multiple spreaders on the spreading[J].Europhysics Letters,2014,106(1):18002. [12]GUO L,LIN J H,GUO Q.Identifying multiple influentialspreaders in term of the distance-based coloring[J].Physics Letters A,2016,380(7/8):837-842. [13]ZHANG J X,CHEN D B,DONG Q.Identifying a set of influential spreaders in complex networks[J].Scientific Reports,2016,6:27823. [14]BIAN T,DENG Y.Identifying influential nodes in complex networks:A node information dimension approach[J].Chaos:An Interdisciplinary Journal of Nonlinear Science,2018,28(4):043109. [15]WANG Z,ZHAO Y,XI J,et al.Fast ranking influential nodes in complex networks using a k-shell iteration factor[J].Physica A: Statistical Mechanics and its Applications,2016,461:171-181. [16]ZAREIE A,SHEIKHAHMADI A,JALILI M.Influential node ranking in social networks based on neighborhood diversity[J].Future Generation Computer Systems,2019,94:120-129. [17]LIU Y,WEI B,DU Y.Identifying influential spreaders byweight degree centrality in complex networks[J].Chaos,Solitons & Fractals,2016,86:1-7. [18]ZENG A,ZHANG C J.Ranking spreaders by decomposing com-plex networks[J].Physics Letters A,2013,377(14):1031-1035. [19]LIU J G,REN Z M,GUO Q.Ranking the spreading influence in complex networks[J].Physica A:Statistical Mechanics and its Applications,2013,392(18):4154-4159. [20]SHEIKHAHMADI A,NEMATBAKHSH M A.Identification of multi-spreader users in social networks for viral marketing[J].Journal of Information Science,2017,43(3):412-423. [21]CARMI S,HAVLIN S,KIRKPATRICK S,et al.A model of Internet topology using k-shell decomposition[J].Proceedings of the National Academy of Sciences,2007,104(27):11150-11154. [22]LUSSEAU D,SCHNEIDER K,BOISSEAU O J.The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405. [23]GLEISER P M,DANON L.Community structure in jazz[J].Advances in Complex Systems,2003,6(4):565-573. [24]NEWMAN M E J.Finding community structure in networksusing the eigenvectors of matrices[J].Physical Review E,2006,74(3):036104. [25]RABADE R,MISHRA N,SHARMA S.Survey of influentialuser identification techniques in online social networks[M]//Recent Advances in Intelligent Informatics.Cham:Springer,2014:359-370. [26]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826. [27]MEHLHORN K,NÄHER S,UHRIG C.The LEDA platformfor combinatorial and geometric computing[C]//International Colloquium on Automata,Languages,and Programming.Berlin:Springer,1997:7-16. [28]SOUAM F,AÏTELHADJ A,BABA-ALI R.Dual modularityoptimization for detecting overlapping communities in bipartite networks[J].Knowledge and Information Systems,2014,40(2):455-488. [29]COLIZZA V,PASTOR-SATORRAS R,VESPIGNANI A.Reaction-diffusion processes and metapopulation models in heterogeneous networks[J].Nature Physics,2007,3(4):276-282. [30]WHITE J G,SOUTHGATE E,THOMSON J N,et al.Thestructure of the nervous system of the nematode Caenorhabditis elegans[J].Philos Trans R Soc Lond B Biol Sci,1986,314(1165):1-340. [31]WEN T,JIANG W.Identifying influential nodes based on fuzzy local dimension in complex networks[J].Chaos,Solitons & Fractals,2019,119:332-342. |
[1] | 郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146 |
[2] | 李其烨, 邢红杰. 基于最大相关熵的KPCA异常检测方法 KPCA Based Novelty Detection Method Using Maximum Correntropy Criterion 计算机科学, 2022, 49(8): 267-272. https://doi.org/10.11896/jsjkx.210700175 |
[3] | 余本功, 张子薇, 王惠灵. 一种融合多层次情感和主题信息的TS-AC-EWM在线商品排序方法 TS-AC-EWM Online Product Ranking Method Based on Multi-level Emotion and Topic Information 计算机科学, 2022, 49(6A): 165-171. https://doi.org/10.11896/jsjkx.210400238 |
[4] | 毛森林, 夏镇, 耿新宇, 陈剑辉, 蒋宏霞. 基于密度敏感距离和模糊划分的改进FCM算法 FCM Algorithm Based on Density Sensitive Distance and Fuzzy Partition 计算机科学, 2022, 49(6A): 285-290. https://doi.org/10.11896/jsjkx.210700042 |
[5] | 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178 |
[6] | 杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 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 |
[7] | 阙华坤, 冯小峰, 刘盼龙, 郭文翀, 李健, 曾伟良, 范竞敏. Grassberger熵随机森林在窃电行为检测的应用 Application of Grassberger Entropy Random Forest to Power-stealing Behavior Detection 计算机科学, 2022, 49(6A): 790-794. https://doi.org/10.11896/jsjkx.210800032 |
[8] | 范静宇, 刘全. 基于随机加权三重Q学习的异策略最大熵强化学习算法 Off-policy Maximum Entropy Deep Reinforcement Learning Algorithm Based on RandomlyWeighted Triple Q -Learning 计算机科学, 2022, 49(6): 335-341. https://doi.org/10.11896/jsjkx.210300081 |
[9] | 王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206 |
[10] | 畅雅雯, 杨波, 高玥琳, 黄靖云. 基于SEIR的微信公众号信息传播建模与分析 Modeling and Analysis of WeChat Official Account Information Dissemination Based on SEIR 计算机科学, 2022, 49(4): 56-66. https://doi.org/10.11896/jsjkx.210900169 |
[11] | 夏源, 赵蕴龙, 范其林. 基于信息熵更新权重的数据流集成分类算法 Data Stream Ensemble Classification Algorithm Based on Information Entropy Updating Weight 计算机科学, 2022, 49(3): 92-98. https://doi.org/10.11896/jsjkx.210200047 |
[12] | 陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177 |
[13] | 赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107 |
[14] | 潘雨, 王帅辉, 张磊, 胡谷雨, 邹军华, 王田丰, 潘志松. 复杂网络社团发现综述 Survey of Community Detection in Complex Network 计算机科学, 2022, 49(11A): 210800144-11. https://doi.org/10.11896/jsjkx.210800144 |
[15] | 原慧琳, 韩真, 冯宠, 黄碧, 刘军涛. 基于核心节点影响力的社区发现方法 Community Discovery Method Based on Influence of Core Nodes 计算机科学, 2022, 49(11A): 211100002-7. https://doi.org/10.11896/jsjkx.211100002 |
|