Computer Science ›› 2023, Vol. 50 ›› Issue (3): 155-163.doi: 10.11896/jsjkx.211200261

• Database & Big Data & Data Science • Previous Articles     Next Articles

Nodes’ Ranking Model Based on Influence Prediction

DUAN Shunran, YIN Meijuan, LIU Fenlin, JIAO Longlong, YU Lanlan   

  1. School of Cyberspace Security,Information Engineering University,Zhengzhou 450001,China
  • Received:2021-12-24 Revised:2022-04-07 Online:2023-03-15 Published:2023-03-15
  • About author:DUAN Shunran,born in 1996,postgra-duate.His main research interests include social network analysis and so on.
    YIN Meijuan,born in 1977,Ph.D,asso-ciate professor,master supervisor.Her main research interests include network data analysis and cyberspace security.
  • Supported by:
    National Natural Science Foundation of China(U1804263) and Zhongyuan Science and Technology Innovation Leading Talent Project(214200510019).

Abstract: The ranking of nodes’ influence has always been a hot issue in the research area of complex networks.Susceptible-infected-recovered(SIR) model is an ideal nodes’ influence ranking method,which is commonly used to evaluate other nodes’ in-fluence ranking methods.But it is difficult to be applied in practice due to its high time complexity.This paper proposes a nodes’ influence ranking model based on sir value learning.Both the local structure and global structure information of nodes are used as features in the model.The sir value learning model is constructed by means of a deep learning model,which is trained on nodes’ features and sir data set in synthetic graphs with the same size.The trained model can predict sir value based on nodes’ features,and then rank nodes’ influence based on predicted sir.In this paper,a specific nodes’ influence ranking method is implemented based on the proposed model,and experiments are carried out on five real networks to verify the effectiveness of the method.The results show that the accuracy and monotonicity of nodes’ influence ranking results are improved compared with degree centrality,Kshell and Weighted Kshell degree neighborhood.

Key words: Complex networks, Nodes’ influence, SIR, Influence ranking

CLC Number: 

  • TP391
[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] LI Jia-wen, GUO Bing-hui, YANG Xiao-bo, ZHENG Zhi-ming. Disease Genes Recognition Based on Information Propagation [J]. Computer Science, 2022, 49(1): 264-270.
[2] WANG Xue-guang, ZHANG Ai-xin, DOU Bing-lin. Non-linear Load Capacity Model of Complex Networks [J]. Computer Science, 2021, 48(6): 282-287.
[3] MA Yuan-yuan, HAN Hua, QU Qian-qian. Importance Evaluation Algorithm Based on Node Intimate Degree [J]. Computer Science, 2021, 48(5): 140-146.
[4] YIN Zi-qiao, GUO Bing-hui, MA Shuang-ge, MI Zhi-long, SUN Yi-fan, ZHENG Zhi-ming. Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network [J]. Computer Science, 2021, 48(5): 184-189.
[5] ZHAO Man-yu, YE Jun. Synchronization of Uncertain Complex Networks with Sampled-data and Input Saturation [J]. Computer Science, 2021, 48(11A): 481-484.
[6] BAO Jun-bo, YAN Guang-hui, LI Jun-cheng. SIR Propagation Model Combing Incomplete Information Game [J]. Computer Science, 2020, 47(6): 230-235.
[7] ZHAO Lei, ZHOU Jin-he. ICN Energy Efficiency Optimization Strategy Based on Content Field of Complex Networks [J]. Computer Science, 2019, 46(9): 137-142.
[8] LIU Xiao-dong, WEI Hai-ping, CAO Yu. Modeling and Stability Analysis for SIRS Model with Network Topology Changes [J]. Computer Science, 2019, 46(6A): 375-379.
[9] SHAN Na, LI Long-jie, LIU Yu-yang, CHEN Xiao-yun. Link Prediction Based on Correlation of Nodes’ Connecting Patterns [J]. Computer Science, 2019, 46(12): 20-25.
[10] FU Li-dong, LI Dan, LI Zhan-li. Following-degree Tree Algorithm to Detect Overlapping Communities in Complex Networks [J]. Computer Science, 2019, 46(12): 322-326.
[11] GAO Hua-bing, SONG Cong-cong, CHEN Bo, LIU Zhi. Traffic Efficiency Analysis of Traffic Road Network Based on Percolation Theory [J]. Computer Science, 2019, 46(11A): 127-133.
[12] SONG Yan-qiu, LI Gui-jun, LI Hui-jia. Community Label Detection Algorithm Based on Potential Background Information [J]. Computer Science, 2018, 45(6A): 314-317.
[13] LUO Jin-liang, JIN Jia-cai and WANG Lei. Evaluation Method for Node Importance in Air Defense Networks Based on Functional Contribution Degree [J]. Computer Science, 2018, 45(2): 175-180.
[14] CEHN Jun-hua, BIAN Zhai-an, LI Hui-jia, GUAN Run-dan. Measuring Method of Node Influence Based on Relative Entropy [J]. Computer Science, 2018, 45(11A): 292-298.
[15] LV Ya-nan, HAN Hua, JIA Cheng-feng, WAN Yan-juan. Link Prediction Algorithm Based on Node Intimate Degree [J]. Computer Science, 2018, 45(11): 92-96.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!