计算机科学 ›› 2018, Vol. 45 ›› Issue (11A): 292-298.

• 网络与通信 • 上一篇    下一篇

基于相对熵的节点影响力测量方法

陈俊华, 边宅安, 李慧嘉, 关闰丹   

  1. 中央财经大学管理科学与工程学院 北京100081
  • 出版日期:2019-02-26 发布日期:2019-02-26
  • 作者简介:陈俊华(1975-),男,博士,副教授,主要研究方向为社会网络;边宅安(1995-),男,硕士生,主要研究方向为复杂网络;李慧嘉(1985-),男,博士,副教授,主要研究方向为复杂网络、数据挖掘、运筹学,E-mail:Hjli@amss.ac.cn;关闰丹(1997-),女,硕士生,主要研究方向为复杂网络。

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

摘要: 识别中心节点是复杂网络分析的一个关键问题。文中结合现有的中心性测度方法,提出了一种利用TOPSIS法的相对熵,以此识别网络中的中心节点。现有的中心性测度方法可以被看作在复杂网络中确定各节点属性的排名。因此,提出的方法可以利用各种中心性测度方法的优点,获得一个更优的排名结果。最后用数值实验验证了所提方法的有效性。

关键词: TOPSIS法, 复杂网络, 相对熵, 中心节点, 中心性测度

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: Centrality measure, Complex networks, Influential nodes, Relative entropy, TOPSIS method

中图分类号: 

  • 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] 郑文萍, 刘美麟, 杨贵.
一种基于节点稳定性和邻域相似性的社区发现算法
Community Detection Algorithm Based on Node Stability and Neighbor Similarity
计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2] 杨波, 李远彪.
数据科学与大数据技术课程体系的复杂网络分析
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
[3] 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超.
比特币实体交易模式分析
Analysis of Bitcoin Entity Transaction Patterns
计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[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] 李家文, 郭炳晖, 杨小博, 郑志明.
基于信息传播的致病基因识别研究
Disease Genes Recognition Based on Information Propagation
计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[8] 吴少波, 傅启明, 陈建平, 吴宏杰, 陆悠.
基于相对熵的元逆强化学习方法
Meta-inverse Reinforcement Learning Method Based on Relative Entropy
计算机科学, 2021, 48(9): 257-263. https://doi.org/10.11896/jsjkx.200700044
[9] 穆俊芳, 郑文萍, 王杰, 梁吉业.
基于重连机制的复杂网络鲁棒性分析
Robustness Analysis of Complex Network Based on Rewiring Mechanism
计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[10] 胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉.
基于复杂网络的全球航空网络结构分析与应用
Analysis and Application of Global Aviation Network Structure Based on Complex Network
计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
[11] 王学光, 张爱新, 窦炳琳.
复杂网络上的非线性负载容量模型
Non-linear Load Capacity Model of Complex Networks
计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040
[12] 马媛媛, 韩华, 瞿倩倩.
基于节点亲密度的重要性评估算法
Importance Evaluation Algorithm Based on Node Intimate Degree
计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184
[13] 殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明.
群智体系网络结构的自治调节:从生物调控网络结构谈起
Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network
计算机科学, 2021, 48(5): 184-189. https://doi.org/10.11896/jsjkx.210200161
[14] 刘胜久, 李天瑞, 谢鹏, 刘佳.
带权图的多重分形度量
Measure for Multi-fractals of Weighted Graphs
计算机科学, 2021, 48(3): 136-143. https://doi.org/10.11896/jsjkx.200700159
[15] 龚追飞, 魏传佳.
基于改进AdaBoost算法的复杂网络链路预测
Link Prediction of Complex Network Based on Improved AdaBoost Algorithm
计算机科学, 2021, 48(3): 158-162. https://doi.org/10.11896/jsjkx.200600075
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!