计算机科学 ›› 2021, Vol. 48 ›› Issue (5): 140-146.doi: 10.11896/jsjkx.200300184

• 数据库&大数据&数据科学 • 上一篇    下一篇

基于节点亲密度的重要性评估算法

马媛媛, 韩华, 瞿倩倩   

  1. 武汉理工大学理学院 武汉430070
  • 收稿日期:2020-03-31 修回日期:2020-06-14 出版日期:2021-05-15 发布日期:2021-05-09
  • 通讯作者: 韩华(Hanhua@whut.edu.cn)
  • 基金资助:
    国家自然科学基金(11601402);国家自然科学基金青年科学基金(111701435);中央高校基本科研业务费(2018IB016)

Importance Evaluation Algorithm Based on Node Intimate Degree

MA Yuan-yuan, HAN Hua, QU Qian-qian   

  1. School of Science,Wuhan University of Technology,Wuhan 430070,China
  • Received:2020-03-31 Revised:2020-06-14 Online:2021-05-15 Published:2021-05-09
  • About author:MA Yuan-yuan,born in 1996,postgra-duate.Her main research interests include complex network and so on.(962031436@qq.com)
    HAN Hua,born in 1975,Ph.D,professor,master supervisor.Her main research interests include complex analysis,economic control and decision-ma-king.
  • Supported by:
    National Natural Science Foundation of China(11601402),Youth Program of National Natural Science Foundation of China(111701435) and Fundamental Research Funds for the Central Universities(2018IB016).

摘要: 识别复杂网络中的重要节点一直是社会网络分析和挖掘领域的热点问题,有助于理解有影响力的传播者在信息扩散和传染病传播中的作用。现有的节点重要性算法充分考虑了邻居信息,但忽略了邻居节点与节点之间的结构信息。针对此问题,考虑到不同结构下邻居节点对节点的影响力不同,提出了一种综合考虑节点的邻居数量和节点与邻居间亲密程度的节点重要性评估算法,其同时体现了节点的度属性和“亲密”属性。该算法利用相似性指标来测量节点间的亲密程度,以肯德尔相关系数为节点排序的准确度评价指标。在多个经典的实际网络上利用SIR(易感-感染-免疫)模型对传播过程进行仿真,结果表明,与度指标、接近中心性指标、介数中心性指标与K-shell指标相比,KI指标可以更精确地对节点传播影响力进行排序。

关键词: 复杂网络, 节点重要性, 亲密度, 相似性

Abstract: Identifying important nodes in complex networks has been a hot topic in the field of social network analysis and mi-ning,which helps to understand the role of influential communicators in information diffusion and the spread of infectious diseases.The existing algorithm of node importance takes neighbor information into account,but ignoring the structure information between node and neighbor node.To solve this problem,considering the different influence of the neighbor node to node under different structures,this paper proposes a node-importance evaluation algorithm that takes into account the number of neighbors of a node and the intimacy between nodes and neighbors,which embodies the degree of node and “intimate” attribute.In this algorithm,similarity index is used to measure the intimacy between nodes,and Kendall correlation coefficient is used to evaluate the accuracy of node ranking.The SIR(susceptible-infected-recovered) model is used to simulate the propagation process on several classical networks.The results show that compared with degree index,closeness centrality index,betweenness centrality index and K-shell index,KI index can rank the propagation influence of nodes more accurately.

Key words: Complex networks, Intimate degree, Node importance, Similarity

中图分类号: 

  • TP393
[1]BARABASI A L,ALBERT R.Emergence of scaling in random networks [J].Science,1999,286(5439):509-512.
[2]JUN T,PIERA M A,RUIZ S.A causal model to explore the ACAS induced collisions [J].Aircraft Engineering and Aerpospace Technology,2014,228(10):1735-748.
[3]WANG X F,LI X,CHEN G R,et al.Complex network theory and its application [M].Beijing:Tsinghua University Press,2006.
[4]LI Y S,MA D Z,ZHANG H G,et al.Critical nodes identification of power systems based on controllability of complex networks [J].Applied Surface Science,2015,5(3):622-636.
[5]MILO R,SHEN-ORR S,ITZKOVITZ S,et al.Network motifs:simple building blocks of complex networks [J].Science,2002,298(5594):824-827.
[6]ALBERT R,JEONG H,BARABASI A L.Diameter of theWorld-Wide Web [J].Nature,1999,401:130-131.
[7]FREEMAN L C.A Set of Measures of Centrality Based on Betweenness [J].Sociometry,1977,40(1):35-41.
[8]SABIDUSSI G.The centrality index of a graph[J].Psy-chometrika,1966,31(4):581-603.
[9]BONACICH P,LLOYD P.Eigenvector-like measures of centra-lity for asymmetric relations [J].Social Networks,2001,23(3):191-201.
[10]RADICCHI F,FORTUNATO S,MARKINES B,et al.Diffusion of scientific credits and the ranking of scientists [J].Physical Review E,2009,80:056103.
[11]LYU 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:10168.
[12]KITSAK M,GALLOS L K,HAVLIN S,et al.Identification of influential spreaders in complex networks [J].Nature Physics,2010,6(11):888-893.
[13]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.
[14]ZENG A,ZHANG C J.Ranking spreaders by decomposing complex networks [J].Physics Letters A,2013,377(14):1031-1035.
[15]MA Q,MA J.Identifying and ranking influential spreaders incomplex networks with consideration of spreading probability [J].Physica A:Statistical Mechanics and its Applications,2017,465:312-330.
[16]WANG H,ZHU M.Hybrid K-shell key node recognition me-thod based on point weight [J].Journal of East China Normal University (Natural Science),2019,3:101-109.
[17]CHEN X,TAN M,ZHAO J,et al.Identifying influential nodes in complex networks based on a spreading influence related centrality [J].Physica A:Statistical Mechanics and its Applications,2019,536:122481.
[18]JIANG L C,JING Y M,HU S Z,et al.Identifying node importance in a complex network based on node bridging feature [J].Applied Surface Science,2018,8:1914.
[19]ZAREIE A,SHEIKHAHMADI A,JALILI M,et al.Influential node ranking in social networks based on neighborhood Diversity [J].Future Generation Computer Systems,2019,94:120-129.
[20]WANG K,WU C X,AI J.Vector centrality measurement me-thod based on multi-order neighborhood shell number [J].Acta Physica Sinica,2019,68(19):196402.
[21]LI C,WANG L,SUN S W,et al.Identification of influential spreaders based on classified neighbors in real-world complex networks [J].Applied Mathematics and Computation,2018,320:512-523.
[22]NEWMAN M E J.Spread of epidemic disease on networks [J].Physical Review E,2002,66:016128.
[23]KENDALL M G.The treatment of ties in ranking problems[J].Biometrika,1945,33:239-251.
[24]NEWMAN M E J.Finding community structure in networksusing the eigenvectors of matrices [J].Physical Review E,2006,74(3):036104.
[25]GLEISER P M,DANON L.Community structure in jazz [J].Advances in complex systems,2003,6(4):565-573.
[26]ZENG A,LIU W.Enhancing network robustness against malicious attacks [J].Physical Review E,2012,85:066130.
[27]GUIMERA R,DANON L,DIAZ-GUILERA A,et al.Self-similar community structure in a network of human interactions [J].Physical Review E,2003,68(6):065103.
[28]BASSETT D S,PORTER M A,WYMBS N F,et al.Robust detection of dynamic community structure in networks [J].Chaos:An Interdisciplinary Journal of Nonlinear Science,2013,23:013142.
[29]DUCH J,ARENAS A.Community detection in complex net-works using extremal optimization [J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2005,72:027104.
[30]VON MERING C,KRAUSE R,SNEL B,et al.Comparative assessment of large-scale data sets of protein-protein interactions[J].Nature,2002,417(6887):399-403.
[1] 郑文萍, 刘美麟, 杨贵.
一种基于节点稳定性和邻域相似性的社区发现算法
Community Detection Algorithm Based on Node Stability and Neighbor Similarity
计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2] 蔡晓娟, 谭文安.
一种改进的融合相似度和信任度的协同过滤算法
Improved Collaborative Filtering Algorithm Combining Similarity and Trust
计算机科学, 2022, 49(6A): 238-241. https://doi.org/10.11896/jsjkx.210400088
[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] 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超.
比特币实体交易模式分析
Analysis of Bitcoin Entity Transaction Patterns
计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[5] 王本钰, 顾益军, 彭舒凡, 郑棣文.
融合动态距离和随机竞争学习的社区发现算法
Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning
计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[6] 陈世聪, 袁得嵛, 黄淑华, 杨明.
基于结构深度网络嵌入模型的节点标签分类算法
Node Label Classification Algorithm Based on Structural Depth Network Embedding Model
计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[7] 郭磊, 马廷淮.
基于好友亲密度的用户匹配
Friend Closeness Based User Matching
计算机科学, 2022, 49(3): 113-120. https://doi.org/10.11896/jsjkx.210200137
[8] 杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞.
基于节点相似性和网络嵌入的复杂网络社区发现算法
Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding
计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009
[9] 赵学磊, 季新生, 刘树新, 李英乐, 李海涛.
基于路径连接强度的有向网络链路预测方法
Link Prediction Method for Directed Networks Based on Path Connection Strength
计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[10] 李家文, 郭炳晖, 杨小博, 郑志明.
基于信息传播的致病基因识别研究
Disease Genes Recognition Based on Information Propagation
计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[11] 罗月童, 汪涛, 杨梦男, 张延孔.
基于历史行车轨迹集的车辆行为可视分析方法
Historical Driving Track Set Based Visual Vehicle Behavior Analytic Method
计算机科学, 2021, 48(9): 86-94. https://doi.org/10.11896/jsjkx.200900040
[12] 郑建炜, 黄娟娟, 秦梦洁, 徐宏辉, 刘志.
基于非局部相似及加权截断核范数的高光谱图像去噪
Hyperspectral Image Denoising Based on Non-local Similarity and Weighted-truncated NuclearNorm
计算机科学, 2021, 48(9): 160-167. https://doi.org/10.11896/jsjkx.200600135
[13] 穆俊芳, 郑文萍, 王杰, 梁吉业.
基于重连机制的复杂网络鲁棒性分析
Robustness Analysis of Complex Network Based on Rewiring Mechanism
计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[14] 何涛, 赵停, 徐鹤.
基于暗通道先验的单幅图像去雾新算法
Novel Algorithm of Single Image Dehazing Based on Dark Channel Prior
计算机科学, 2021, 48(7): 219-224. https://doi.org/10.11896/jsjkx.200700160
[15] 胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉.
基于复杂网络的全球航空网络结构分析与应用
Analysis and Application of Global Aviation Network Structure Based on Complex Network
计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!