Computer Science ›› 2018, Vol. 45 ›› Issue (11A): 292-298.

• Network & Communication • Previous Articles     Next Articles

Measuring Method of Node Influence Based on Relative Entropy

CEHN Jun-hua, BIAN Zhai-an, LI Hui-jia, GUAN Run-dan   

  1. School of Management Science and Engineering,Central University of Finance and Economics,Beijing 100081,China
  • Online:2019-02-26 Published:2019-02-26

Abstract: Recognizing central nodes is a key problem in complex network analysis,this paper proposed a method of relative entropy using TOPSIS (Technique for Order Performance by Similarity to Ideal Solution) method to identify the influential node in the network.The existing central measure methods can be considered as determining the rank of each node attribute in a complex network.Therefore,the method proposed in this paper can use the advantages of various central measure methods to obtain a better ranking result.Finally,the validity of the proposed method was verified by numerical experiments.

Key words: Complex networks, Influential nodes, Centrality measure, Relative entropy, TOPSIS method

CLC Number: 

  • TP393
[1]TAN S,LÜ J.Characterizing the effect of population heterogeneity on evolutionary dynamics on complex networks[J].Scientific Reports,2014,4(4):5034.
[2]LU J,CHEN G.A time-varying complex dynamical network model and its controlled synchronization criteria[J].IEEE Transactions on Automatic Control,2005,50(6):841-846.
[3]LI X,YANG D,LIU X,et al.Bridging Time Series Dynamics and Complex Network Theory with Application to Electrocar-diogram Analysis[J].Circuits & Systems Magazine IEEE,2012,12(4):33-46.
[4]LU W,LI X,RONG Z.Global stabilization of complex networks with digraph topologies via a local pinning algorithm[J].Automatica,2010,46(1):116-121.
[5]JIN Q,WANG L,XIA C Y,et al.Spontaneous Symmetry Brea-king in Interdependent Networked Game[J].Sci. Rep.,2012,4(6172):4095.
[6]BOZZO E,FRANCESCHET M.Resistance distance,closeness,and betweenness[J].Social Networks,2013,35(3):460-469.
[7]WANG W,TANG M,YANG H,et al.Asymmetrically interacting spreading dynamics on complex layered networks[J].Scientific Reports,2014,4(7502):5097.
[8]WANG Z,KOKUBO S,JUSUP M,et al.Universal scaling for the dilemma strength in evolutionary games[J].Physics of Life Reviews,2015,14:47-48.
[9]STROGATZ S H.Exploring Complex Networks.Nature 410,268[J].Nature,2001,410(6825):268-276.
[10]NEWMAN M E.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.
[11]LÜ L,ZHOU T.Link prediction in complex networks: A survey[J].Physica A Statistical Mechanics & Its Applications,2011,390(6):1150-1170.
[12]SCHADT E E.Molecular networks as sensors and drivers of common human diseases[J].Nature,2009,461(7261):218.
[13]AMANCIO D R,NUNES M G V,JR O N O,et al.Using metrics from complex networks to evaluate machine translation[J].Physica A Statistical Mechanics & Its Applications,2011,390(1):131-142.
[14]YANG M,CHEN G,FU X.A modified SIS model with an infective medium on complex networks and its global stability[J].Physica A Statistical Mechanics & Its Applications,2011,390(12):2408-2413.
[15]MOTTER A E,LAI Y C.Cascade-based attacks on complex networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2002,66(2):065102.
[16]TAO Z,BING-HONG W.Catastrophes in scale-free networks[J].Chinese Physics Letters,2005,22(5):1072-1075.
[17]PASTORSATORRAS R,VESPIGNANI A.Immunization of complex networks[J].Phys Rev E Stat Nonlin Soft Matter Phys,2002,65(3 Pt 2A):036104.
[18]ZHAO M,ZHOU T,WANG B H,et al.Enhanced synchroni-zability by structural perturbations[J].Phys. Rev. E,2005,72(5 Pt 2):057102.
[19]ZEMANOVÁ L,ZHOU C,KURTHS J.Structural and functional clusters of complex brain networks[J].Physica D Nonli-near Phenomena,2006,224(1):202-212.
[20]CHEN D B,XIAO R,ZENG A,et al.Path diversity improvesthe identification of influential spreaders[J].Europhysics Letters,2013,104(6):68006.
[21]MOTTER A E,ZHOU C,KURTHS J.Enhancing complex-network synchronization[J].Europhysics Letters,2005,69(3):334.
[22]BARABÁSI A L,GULBAHCE N,LOSCALZO J.Network medicine: a network-based approach to human disease[J].Nature Reviews Genetics,2011,12(1):56.
[23]YANG R,WANG B H,REN J,et al.Epidemic spreading on he-terogeneous networks with identical infectivity[J].Physics Letters A,2007,364(3):189-193.
[24]BORGE-HOLTHOEFER J,MORENO Y.Absence of influential spreaders in rumor dynamics[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2012,85(2 Pt 2):026116.
[25]GLATTFELDER J B.The Network of Global Corporate Control[J].Business & Politics,2011,15(3):357-379.
[26]FREEMAN L C.Centrality in social networks conceptual clarification[J].Social Networks,1978,1(3):215-239.
[27]BONACICH P,LLOYD P.Eigenvector-like measures of centra-lity for asymmetric relations[J].Social Networks,2001,23(3):191-201.
[28]BRIN S,PAGE L.Reprint of:The anatomy of a large-scale hypertextual web search engine[J].Computer Networks,2014,56(18):3825-3833.
[29]LÜ L,ZHANG Y C,CHI H Y,et al.Leaders in Social Net-works,the Delicious Case[J].Plos One,2011,6(6):e21202.
[30]KITSAK M,GALLOS L K,HAVLIN S,et al.Identification of influential spreaders in complex networks[J].Nature Physics,2010,6(11):888-893.
[31]LIU J G,REN Z M,GUO Q.Ranking the spreading influence in complex networks[J].Physica A Statistical Mechanics & Its Applications,2013,392(18):4154-4159.
[32]DU Y,GAO C,HU Y,et al.A new method of identifying influential nodes in complex networks based on TOPSIS[J].Physica A:Statistical Mechanics and its Applications,2014,399:57-69.
[33]BAUER F,LIZIER J T.Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach[J].Epl,2012,99(6):367-372.
[34]WEI D,DENG X,ZHANG X,et al.Identifying influential nodes in weighted networks based on evidence theory[J].Physica A Statistical Mechanics & Its Applications,2013,392(10):2564-2575.
[35]GAO C,WEI D,HU Y,et al.A modified evidential methodology of identifying influential nodes in weighted networks[J].Physica A Statistical Mechanics & Its Applications,2013,392(21):5490-5500.
[36]GAO C,LAN X,ZHANG X,et al.A Bio-Inspired Methodology of Identifying Influential Nodes in Complex Networks[J].Plos One,2013,8(6):e66732.
[37]GÓMEZABC D.Modeling centrality measures in social network analysis using bi-criteria network flow optimization problems[J].European Journal of Operational Research,2013,226(2):354-365.
[38]OPSAHL T,AGNEESSENS F,SKVORETZ J.Node centrality in weighted networks: Generalizing degree and shortest paths[J].Social Networks,2010,32(3):245-251.
[39]KRACKHARDT D.Assessing the Political Landscape: Structure,Cognition,and Power in Organizations[J].Administrative Science Quarterly,1990,35(2):342-369.
[40]BONACICH P.Factoring and weighting approaches to status scores and clique identification[J].Journal of Mathematical Sociology,1972,2(1):113-120.
[41]KULLBACK S,LEIBLER R A.On Information and Sufficiency[J].Annals of Mathematical Statistics,1951,22(1):79-86.
[42]COVER T M,THOMAS J A.Elements of Information Theory Wiley[J].New York,1991.
[43]HWANG C L,YOON K.Methods for Multiple Attribute Decision Making[M]∥Multiple Attribute Decision Making.Sprin-ger Berlin Heidelberg,1981:58-191.
[44]GUO X Z,XIN X L.Partial Entropy and Relative Entropy of Fuzzy Sets[J].Fuzzy Systems & Mathematics,2005(2):97-102.
[45]GUIMERÃ R,DANON L,DÃAZ-GUILERA A,et al.Self-similar community structure in a network of human interactions[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2003,68(6 Pt 2):065103.
[46]ZACHARY W W.An Information Flow Model for Conflict and Fission in Small Groups[J].Journal of Anthropological Research,1977,33(4):452-473.
[47]NEWMAN M E J.Finding community strcuture in networks using the eigenvectors of matrics.Phys.Rev.E 74,036104[J].Physical Review E,2006,74(3 Pt 2):036104.
[48]ZHOU T,LIU J G,BAI W J,et al.Behaviors of susceptible-infected epidemics on scale-free networks with identical infectivity[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2006,74(2):056109.
[49]BAI W J,ZHOU T,WANG B H.Immunization of susceptible-infected model on scale-free networks[J].Physica A Statistical Mechanics & Its Applications,2007,384(2):656-662.
[50]KARSAI M,KIVELÄ M,PAN R K,et al.Small but slow world: how network topology and burstiness slow down spreading[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2011,83(2):025102.
[1] 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.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] LU Yi-hong, ZHANG Zhen-ning and YANG Xiong. Community Structure Detection Algorithm Based on Nodes’ Eigenvectors [J]. Computer Science, 2017, 44(Z6): 419-423.
[10] JIANG Mao-sheng, GE Jian-fei and CHEN Ling. Link Prediction in Networks with Node Attributes Based on Space Mapping [J]. Computer Science, 2017, 44(7): 257-261.
[11] ZHOU Xian-ting, HUANG Wen-ming and DENG Zhen-rong. Micro-blog Retweet Behavior Prediction Algorithm Based on Anomaly Detection and Random Forest [J]. Computer Science, 2017, 44(7): 191-196.
[12] TONG Lin-ping, XU Shou-zhi, ZHOU Huan and JIANG Ting-yao. Research on Temporal Centrality Prediction of Nodes in Complex Networks [J]. Computer Science, 2017, 44(10): 122-126.
[13] CHEN Xu and CHEN Ke-jia. Improved Link Prediction Method for Weighted Networks [J]. Computer Science, 2017, 44(10): 96-98.
[14] ZHANG Li and AN Xin-lei. Research on Adaptive Synchronization Based on Complex Network with Multi-weights [J]. Computer Science, 2016, 43(Z11): 286-289.
[15] CHEN Yong-xiang and CHEN Ling. Link Prediction in Networks with Node Attributes Based on Random Walks Algorithm [J]. Computer Science, 2016, 43(6): 199-203.
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .