基于多属性决策的复杂网络节点重要性综合评价方法

于会; 刘尊; 李勇军

doi:10.7498/aps.62.020204

摘要

复杂网络中的节点重要性评价在实际应用中有着重要意义.现有的一些重要性评价指标如度、介数等存在适用范围有限,评价结果不够全面等缺点,因为节点在复杂网络中的重要性不仅仅受单一因素的影响.为此,本文提出了一种基于多属性决策的复杂网络节点重要性综合评价方法. 该方法将复杂网络中的每一个节点看作一个方案,其多个重要性评价指标作为该方案的属性, 通过计算每个方案到理想方案的接近程度,最终得到该节点的重要性综合评价结果. 该方法不仅可以用于不同类型复杂网络的节点重要性评价,而且便于扩展, 实验结果表明了该方法的有效性.

关键词:

Abstract

In complex networks, it is significant how to rank the nodes according to their importance. Most of the existing methods of ranking key nodes (e.g. degree-based, betweenness-based) only consider one factor but not the integration of whole complex network in evaluating the importance of nodes, so those methods each have a limited application range. In this paper, a multi-attribute decision-making method to identify the key nodes in complex networks is proposed. In our method, each node is regarded as a solution, and each importance evaluation criterion as one solution's attribute. After that, we calculate the closeness between each solution and the ideal solution in order to obtain the integration results of node importance in complex networks. The proposed method can be used in a variety of complex networks. It is also easy to evaluate the importance evaluation criteria. Finally, experimental results show that the proposed method is effective.

Keywords:

作者及机构信息

1.
西北工业大学计算机学院, 西安 710072

基金项目: 西北工业大学基础研究基金 (批准号: NPU-FFR-JC201257)、航空科学基金 (批准号: 2010ZC53031)、国家部委预研基金 (批准号: NBDA0001)和东南大学计算机网络与信息集成教育部重点实验室开放基金 (批准号: K93-9-2010-09)资助的课题.

Authors and contacts

1.
School of Computer Science, Northwestern Polytechnical University, Xi'an 710072, China

Funds: Project supported by NPU Foundation for Fundamental Research of China (Grant No. NPU-FFR-JC201257), the Aviation Science Fund of China (Grant No. 2010ZC53031), the Advanced Research Fund of Ministry of China (Grant No. NBDA0001), the Open Research Fund from Key Laboratory of Computer Network and Information Integration (Southeast University), and the Ministry of Education, China (Grant No. K93-9-2010-09)).

参考文献

[1]	Barabási A L, Bonabeau E 2003 Sci. Am. 288 50
[2]	Chen H, Chung W, Xu J J, Wang G, Qin Y, Chau M 2004 Computer 37 50
[3]	L T Y, Piao X F, Xie W Y, Huang S B 2012 Acta Phys. Sin. 61 170512 (in Chinese) [吕天阳, 朴秀峰, 谢文艳, 黄少滨 2012 61 170512]
[4]	Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹, 李翔, 汪小帆 2007 56 1313]
[5]	Xiong X, Hu Y 2012 Acta Phys. Sin. 61 150509 (in Chinese) [熊熙, 胡勇 2012 61 150509]
[6]	Budak C, Agrawal D, Abbadi A E 2011 Proceedings of the International World Wide Web Conference Committee Hyderabad, India, March 28-April 1, 2011 p665
[7]	Zhang Y C, Liu Y, Zhang H F, Cheng H, Xiong F 2011 Acta Phys. Sin. 60 050501 (in Chinese) [张彦超, 刘云, 张海峰, 程辉, 熊菲 2011 60 050501]
[8]	Yan R, Tang J, Liu X B 2011 Proceedings of the 20th ACM international conference on Information and knowledge management, Glasgow, Scotland, UK, October 24-28, 2011 p1247
[9]	Watts D J, Dodds P S, Newman M E J 2002 Science 296 1302
[10]	Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106 (in Chinese) [刘宏鲲, 周涛 2007 56 106]
[11]	Cai K Q, Zhang Jun, Du W B, Cao X B 2012 Chin. Phys. B 21 028903
[12]	Wang G Z, Gao Y J, Bao Z J, Han Z X 2009 Acta Phys. Sin. 58 3597 (in Chinese) [王光增, 曹一家, 包哲静, 韩帧祥 2009 58 3597]
[13]	Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101
[14]	An S H, Du Y B, Qu J L 2006 Chin. J. Manage. Sci. 14 106 (in Chinese) [安世虎, 都艺兵, 曲吉林 2006 中国管理科学 14 106]
[15]	Corley H W, Sha D Y 1982 Oper. Res. Letters 1 157
[16]	Nardelli E, Proietti G, Widmayer P 2001 Info. Proc. Letters 79 81
[17]	Tan Y J, Wu J, Deng H Z 2006 Syst. Eng. Theory & Practice 26 79 (in Chinese) [谭跃进, 吴俊, 邓宏钟 2006 系统工程理论与实践 26 79]
[18]	Freeman L C, Borgatti S P, White D R 1991 Soc. Networks 13 141
[19]	Luo J D 2010 Social Network Analysis (2st Ed.) (Beijing: Social Science Academic Press) p187 (in Chinese) [罗家德 2010 社会网分析讲义(北京:社会科学文献出版社) 第187页]
[20]	Estrada E, Rodríguez-Velázquez J A 2005 Phy. Rev. E 71 056103
[21]	Perra N, Fortunato S 2008 Phy. Rev. E 78 036107
[22]	Newman M E J 2005 Soc. Networks 27 39
[23]	Dou F L, Hu Y Q, Li Y, Fan Y, Di Z R Acta Phys. Sin. 61 178901 (in Chinese) [钭斐玲, 胡延庆, 黎勇, 樊瑛, 狄增如 2012 61 178901]
[24]	Tzeng G H, Huang J J 2011 Multiple Attribute Decision Making: Methods and Applications (CRC: Boca Raton London New York) p69
[25]	Wang X F, Li X, Chen G R 2012 Network Science: An Introduction (1st Ed.) (Beijing: Higher Education Press) p161 (in Chinese) [汪小帆, 李翔, 陈关荣 2012 网络科学导论(北京:高等教育出版社) 第161页]
[26]	Freeman L C A 1977 Sociometry 40 35
[27]	Burt R S 2004 Am. J. Sociol. 110 349
[28]	Zhu Y, Meng Z Y, Kan S Y 1999 J. Northern Jiaotong University 23 119 (in Chinese) [朱茵, 孟志勇, 阚叔愚 1999 北方交通大学学报 23 119]
[29]	Zhou X, Zhang F M, Li K W, Hui X B, Wu H S 2012 Acta Phys. Sin. 61 050201 (in Chinese) [周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜 2012 61 050201]
[30]	Chen Y, Hu A Q, Hu X 2004 J. China Institute Commun. 25 129 (in Chinese) [陈勇, 胡爱群, 胡啸 2004 通信学报 25 129]
[31]	Zhao Y H,Wang Z L, Zheng J, Guo X J 2009 J. Beijing University of Aeronautics and Astronautics 35 1076 (in Chinese) [赵毅寰, 王祖林, 郑晶, 郭旭静 2009 北京航空航天大学学报 35 1076]

施引文献

[1]	Barabási A L, Bonabeau E 2003 Sci. Am. 288 50
[2]	Chen H, Chung W, Xu J J, Wang G, Qin Y, Chau M 2004 Computer 37 50
[3]	L T Y, Piao X F, Xie W Y, Huang S B 2012 Acta Phys. Sin. 61 170512 (in Chinese) [吕天阳, 朴秀峰, 谢文艳, 黄少滨 2012 61 170512]
[4]	Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹, 李翔, 汪小帆 2007 56 1313]
[5]	Xiong X, Hu Y 2012 Acta Phys. Sin. 61 150509 (in Chinese) [熊熙, 胡勇 2012 61 150509]
[6]	Budak C, Agrawal D, Abbadi A E 2011 Proceedings of the International World Wide Web Conference Committee Hyderabad, India, March 28-April 1, 2011 p665
[7]	Zhang Y C, Liu Y, Zhang H F, Cheng H, Xiong F 2011 Acta Phys. Sin. 60 050501 (in Chinese) [张彦超, 刘云, 张海峰, 程辉, 熊菲 2011 60 050501]
[8]	Yan R, Tang J, Liu X B 2011 Proceedings of the 20th ACM international conference on Information and knowledge management, Glasgow, Scotland, UK, October 24-28, 2011 p1247
[9]	Watts D J, Dodds P S, Newman M E J 2002 Science 296 1302
[10]	Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106 (in Chinese) [刘宏鲲, 周涛 2007 56 106]
[11]	Cai K Q, Zhang Jun, Du W B, Cao X B 2012 Chin. Phys. B 21 028903
[12]	Wang G Z, Gao Y J, Bao Z J, Han Z X 2009 Acta Phys. Sin. 58 3597 (in Chinese) [王光增, 曹一家, 包哲静, 韩帧祥 2009 58 3597]
[13]	Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101
[14]	An S H, Du Y B, Qu J L 2006 Chin. J. Manage. Sci. 14 106 (in Chinese) [安世虎, 都艺兵, 曲吉林 2006 中国管理科学 14 106]
[15]	Corley H W, Sha D Y 1982 Oper. Res. Letters 1 157
[16]	Nardelli E, Proietti G, Widmayer P 2001 Info. Proc. Letters 79 81
[17]	Tan Y J, Wu J, Deng H Z 2006 Syst. Eng. Theory & Practice 26 79 (in Chinese) [谭跃进, 吴俊, 邓宏钟 2006 系统工程理论与实践 26 79]
[18]	Freeman L C, Borgatti S P, White D R 1991 Soc. Networks 13 141
[19]	Luo J D 2010 Social Network Analysis (2st Ed.) (Beijing: Social Science Academic Press) p187 (in Chinese) [罗家德 2010 社会网分析讲义(北京:社会科学文献出版社) 第187页]
[20]	Estrada E, Rodríguez-Velázquez J A 2005 Phy. Rev. E 71 056103
[21]	Perra N, Fortunato S 2008 Phy. Rev. E 78 036107
[22]	Newman M E J 2005 Soc. Networks 27 39
[23]	Dou F L, Hu Y Q, Li Y, Fan Y, Di Z R Acta Phys. Sin. 61 178901 (in Chinese) [钭斐玲, 胡延庆, 黎勇, 樊瑛, 狄增如 2012 61 178901]
[24]	Tzeng G H, Huang J J 2011 Multiple Attribute Decision Making: Methods and Applications (CRC: Boca Raton London New York) p69
[25]	Wang X F, Li X, Chen G R 2012 Network Science: An Introduction (1st Ed.) (Beijing: Higher Education Press) p161 (in Chinese) [汪小帆, 李翔, 陈关荣 2012 网络科学导论(北京:高等教育出版社) 第161页]
[26]	Freeman L C A 1977 Sociometry 40 35
[27]	Burt R S 2004 Am. J. Sociol. 110 349
[28]	Zhu Y, Meng Z Y, Kan S Y 1999 J. Northern Jiaotong University 23 119 (in Chinese) [朱茵, 孟志勇, 阚叔愚 1999 北方交通大学学报 23 119]
[29]	Zhou X, Zhang F M, Li K W, Hui X B, Wu H S 2012 Acta Phys. Sin. 61 050201 (in Chinese) [周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜 2012 61 050201]
[30]	Chen Y, Hu A Q, Hu X 2004 J. China Institute Commun. 25 129 (in Chinese) [陈勇, 胡爱群, 胡啸 2004 通信学报 25 129]
[31]	Zhao Y H,Wang Z L, Zheng J, Guo X J 2009 J. Beijing University of Aeronautics and Astronautics 35 1076 (in Chinese) [赵毅寰, 王祖林, 郑晶, 郭旭静 2009 北京航空航天大学学报 35 1076]

[1]	王博雅, 杨小春, 卢升荣, 唐勇平, 洪树权, 蒋惠园. 基于图卷积神经网络的多维度节点重要性评估方法. , 2024, 73(22): 226401. doi: 10.7498/aps.73.20240937
[2]	汪亭亭, 梁宗文, 张若曦. 基于信息熵与迭代因子的复杂网络节点重要性评价方法. , 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
[3]	阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. , 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
[4]	杨松青, 蒋沅, 童天驰, 严玉为, 淦各升. 基于Tsallis熵的复杂网络节点重要性评估方法. , 2021, 70(21): 216401. doi: 10.7498/aps.70.20210979
[5]	黄丽亚, 汤平川, 霍宥良, 郑义, 成谢锋. 基于加权K-阶传播数的节点重要性. , 2019, 68(12): 128901. doi: 10.7498/aps.68.20190087
[6]	孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. , 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
[7]	王雨, 郭进利. 基于多重影响力矩阵的有向加权网络节点重要性评估方法. , 2017, 66(5): 050201. doi: 10.7498/aps.66.050201
[8]	阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. , 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
[9]	侯绿林, 老松杨, 肖延东, 白亮. 复杂网络可控性研究现状综述. , 2015, 64(18): 188901. doi: 10.7498/aps.64.188901
[10]	韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. , 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
[11]	滕启治, 谭欣, 武紫玉, 沈俊, 王海峰. 大型水轮发电机冷却方式综合评价方法的研究. , 2015, 64(17): 178802. doi: 10.7498/aps.64.178802
[12]	刘金良. 具有随机节点结构的复杂网络同步研究. , 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
[13]	任卓明, 邵凤, 刘建国, 郭强, 汪秉宏. 基于度与集聚系数的网络节点重要性度量方法研究. , 2013, 62(12): 128901. doi: 10.7498/aps.62.128901
[14]	刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. , 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
[15]	吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. , 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
[16]	吕天阳, 谢文艳, 郑纬民, 朴秀峰. 加权复杂网络社团的评价指标及其发现算法分析. , 2012, 61(21): 210511. doi: 10.7498/aps.61.210511
[17]	周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. , 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
[18]	周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. , 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
[19]	吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. , 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
[20]	李季, 汪秉宏, 蒋品群, 周涛, 王文旭. 节点数加速增长的复杂网络生长模型. , 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051

计量

文章访问数: 10139
PDF下载量: 2341
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

搜索

留言板