基于重要度传输矩阵的复杂网络节点重要性辨识方法

doi:10.3969/j.issn.0372-2112.2020.12.016

电子学报 ›› 2020, Vol. 48 ›› Issue (12): 2402-2408.DOI: 10.3969/j.issn.0372-2112.2020.12.016

基于重要度传输矩阵的复杂网络节点重要性辨识方法

胡钢¹, 高浩¹, 徐翔², 许丽鹏¹

1. 安徽工业大学管理科学与工程学院, 安徽马鞍山 243032;
2. 国防科技大学信息系统工程重点实验室, 湖南长沙 410073

收稿日期:2019-07-04 修回日期:2020-07-22 出版日期:2020-12-25
- 作者简介:
- 胡钢男,1970年出生,甘肃天水人,博士后,副教授主要研究方向为复杂网络系统建模仿真与均衡分析、多属性决策.E-mail:hug_2004@126.com;高浩男,1995年出生,安徽宿州人,现为在读硕士研究生,主要研究方向为复杂网络系统建模仿真与均衡分析、多属性决策.E-mail:872165680@qq.com

Importance Identification Method of Complex Network Nodes Based on Importance Transfer Matrix

HU Gang¹, GAO Hao¹, XU Xiang², XU Li-peng¹

1. School of Management Science and Engineering, Anhui University of Technology, Maanshan, Anhui 243032, China;
2. Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha, Hunan 410073, China

Received:2019-07-04 Revised:2020-07-22 Online:2020-12-25 Published:2020-12-25

摘要/Abstract

摘要： 复杂网络中节点重要性辨识对分析网络结构和功能具有重要作用.为了辨识节点重要性，分析节点自身和关联节点的作用，本文构建了一种基于重要度传输矩阵的节点重要性辨识模型.首先，基于关联节点与节点之间的最优路径长度、最优路径数目和信息传播率定义了节点间的传输能力.其次，依据度值和传输能力构建重要度传输矩阵，综合节点局部重要性和全局属性指标评价节点的重要性.最后，对"ARPA"网络和四个真实网络进行破坏性仿真分析，结果本文方法表明对网络造成更大的破坏，证明了该方法的有效性和可靠性.

关键词: 复杂网络, 节点重要性, 信息传播率, 传输能力, 重要度传输矩阵

Abstract: In complex networks, node importance identification plays an important role in analyzing the structure and function. In order to identify the node's importance and analyze the role of nodes themselves and associated nodes, we construct a node importance identification model based on importance transfer matrix. Firstly, the transmission capability between nodes is defined based on the optimal path length, the number of optimal paths and the information propagation rate between the associated nodes and the nodes. Secondly, the node degree and transmission capacity are used to construct the importance transmission matrix, and the local importance and global attribute index of the node are integrated to evaluate the importance of the node. Finally, destructive simulation analysis on the "ARPA" network and four real networks show that this method causes more damage to the network, which proves the method's effectiveness and reliability.

Key words: complex network, node's importance, information transmission rate, transmission capacity, importance transfer matrix

中图分类号:

TP393

胡钢, 高浩, 徐翔, 等. 基于重要度传输矩阵的复杂网络节点重要性辨识方法[J]. 电子学报, 2020, 48(12): 2402-2408.

HU Gang, GAO Hao, XU Xiang, et al. Importance Identification Method of Complex Network Nodes Based on Importance Transfer Matrix[J]. Acta Electronica Sinica, 2020, 48(12): 2402-2408.

参考文献

[1] Zhang Y,Yang N,Lall U.Modeling and simulation of the vulnerability of interdependent power-water infrastructure networks to cascading failures[J].Journal of Systems Science and Systems Engineering,2016,25(1):102-118.
[2] Barabási A L,Bonabeau E.Scale-free networks[J].Scientific American,2003,288(5):60-69.
[3] Albert R,Jeong H,Barabasi.The diameter of the world wide web[J].Nature,1999,401(06):130-131.
[4] Freeman L C.A Set of measures of centrality based on betweenness[J].Sociometry,1977,40(01):35-41.
[5] Borgatti S P,Everett M G.A graph-theoretic perspective on centrality[J].Social Networks,2006,28(04):466-484.
[6] Hage P,Harary F.Eccentricity and centrality in networks[J].Social Networks,1995,17(1):57-63.
[7] Kitsak M,Gallosl K,Havlin S,et al.Identification of influential spreaders in complex networks[J].Nature Physics,2010,6(11):888-893.
[8] 韩忠明,陈炎,李梦琪,等.一种有效的基于三角结构的复杂网络节点影响力度量模型[J].物理学报, 2016,65(16):168901-1-168901-12. Han Zhong-Ming,Chen Yan,Li Meng-Qi,et al.An efficient node influence metric based on triangle in complex networks[J].Acta Physica Sinica,2016,65(16):168901-1-168901-12.(in Chinese)
[9] 马润年,王班,王刚,等.基于互信息的通信网络节点重要性度量方法[J].电子学报,2017,45(03):747-752. Ma Run-Nian,Wang Ban,Wang Gang,et al.Evaluation method for node importance in communication network based on mutual information[J].Acta Electronica Sinica,2017,45(03):747-752.(in Chinese)
[10] 于会,刘尊,李勇军,等.一种基于多属性决策的复杂网络节点重要度综合评价方法[J].物理学报,2013,62(02):020204-1-020204-9. Yu Hui,Liu Zun,Li Yong-Jun,et al.Key nodes in complex networks identified by multi-attribute decision-making method[J].Acta Physica Sinica,2013,62(2):020204-1-020204-9.(in Chinese)
[11] 赵毅寰,王祖林,郑晶,等.利用重要性贡献矩阵确定通信网中最重要节点[J].北京航空航天大学学报,2009,35(9):1076-1079. Zhao Yi-Huan,Wang Zu-Lin,Zheng Jing,et al.Finding most vital node by node importance contribution matrix in communication networks[J].Journal of Beijing University of Aeronautics and Astronautics,2009.35(9):1076-1079.(in Chinese)
[12] 周漩,张凤鸣,李克武,等.利用重要度评价矩阵确定复杂网络关键节点[J].物理学报,2012,61(5):050201-1-050201-7 Zhou Xuan,Zhang Feng-Ming,Li Ke-Wu,et al.Finding vital node by node importance evaluation matrix in complex networks[J].Acta Physica Sinica,2012,61(5):050201-1-050201-7.(in Chinese)
[13] Fowler J H,Christakis.Dynamic spread of happiness in a large social network:longitudinal analysis over 20 years in the Framingham heart study[J].BMJ,2008,337:1-9.
[14] 范文礼,刘志刚.基于传输效率矩阵的复杂网络节点重要度排序方法[J].西南交通大学学报,2014,49(02):337-342. Fan Wen-Li,Liu Zhi-Gang.Ranking method for node importance based on efficiency matrix[J].Journal of Southwest Jiaotong University,2014,49(02):337-342.(in Chinese)
[15] Hu P,Fan W,Mei S.Identifying node importance in complex networks[J].Physical A:Statistical Mechanics and its Applications,2015,429:169-176.
[16] Burt R S.Structural holes and good ideas[J].American Journal of Sociology,2004,110(2):349-399.
[17] Zhong-kui Bao,Chuang Ma,et al.Identification of influential nodes in complex networks:Method from spreading probability viewpoint[J].Physica A Statistical Mechanics & Its Applications,2017,468:391-397.
[18] Griffith D A,Chun Y.Spatial autocorrelation in spatial interactions models:geographic scale and resolution implications for network resilience and vulnerability[J].Networks & Spatial Economics,2015,15(2):337-365.
[19] 蔡青松,刘燕,牛建伟,等.一种关注消息时效性的机会社会网络中节点传播能力分析模型[J].电子学报,2015,43(9):1705-1713. Cai Qing-song,Liu Yan,Niu Jian-wei,et al.An analytical model for ranking the candidates of disseminating time-bound messages in opportunistic mobile social networks[J].Acta Electronica Sinica,2015,43(9):1705-1713.(in Chinese)
[20] Page L B,Perry J E.Reliability polynomials and link importance in networks[J].Reliability IEEE Transactions on,1994,43(1):51-58.
[21] Blagus N,Šubelj L,Bajec M.Self-similar scaling of density in complex real-world networks[J].Physica A:Statistical Mechanics and its Applications,2012,391(8):2794-2802.
[22] J Kunegis.Hamsterster Full Network Dataset-KONECT[DB/OL].http://konect.uni-koblenz.de/networks/petster-hamster,2019-06-10.
[23] Leskovec J,Kleinberg J,Faloutsos C.Graph evolution:densification and shrinking diameters[J].ACM Transactions on Knowledge Discovery from Data,2007,1(1):1-42.
[24] Newman M E.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences of the United States of America,2001,98(2):404-409.

基于重要度传输矩阵的复杂网络节点重要性辨识方法

Importance Identification Method of Complex Network Nodes Based on Importance Transfer Matrix

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	胡钢, 牛琼, 许丽鹏, 卢志宇, 过秀成. 基于网络超链接信息熵的节点重要性序结构演化建模分析[J]. 电子学报, 2022, 50(11): 2638-2644.
[2]	张磊, 刘庆, 杨尚尚, 杨海鹏, 程凡, 马海平. 基于双编码的重叠社团检测多目标优化方法[J]. 电子学报, 2021, 49(11): 2101-2107.
[3]	胡钢, 徐翔, 张维明, 周鋆. 基于主成分分析的网络节点重要性指标贡献评价[J]. 电子学报, 2019, 47(2): 358-365.
[4]	王尔申, 王玉伟, 庞涛, 曲萍萍, 姜毅. 基于边攻击成本的复杂网络鲁棒性研究[J]. 电子学报, 2018, 46(5): 1166-1172.
[5]	何鹏, 王鹏, 李兵, 胡思文. 基于多粒度软件网络模型的软件系统演化分析[J]. 电子学报, 2018, 46(2): 257-267.
[6]	马润年, 王班, 王刚, 郭晓成, 刘文斌. 基于互信息的通信网络节点重要性度量方法[J]. 电子学报, 2017, 45(3): 747-752.
[7]	刘世超, 朱福喜, 冯曦. 复杂网络的重叠社区及社区间的结构洞识别[J]. 电子学报, 2016, 44(11): 2600-2606.
[8]	王诗懿, 董一鸿, 李志超, 陈华辉, 钱江波. 大规模复杂网络下重叠社区的识别[J]. 电子学报, 2015, 43(8): 1575-1582.
[9]	国琳, 左万利. 基于兴趣图谱的用户兴趣分布分析及专家发现[J]. 电子学报, 2015, 43(8): 1561-1567.
[10]	张健沛, 邓琨, 杨静, 刘星妍. 基于边标签传播的复杂网络社区识别方法[J]. 电子学报, 2015, 43(6): 1113-1118.
[11]	冷作福. 基于贪婪优化技术的网络社区发现算法研究[J]. 电子学报, 2014, 42(4): 723-729.
[12]	潘伟丰, 李兵, 马于涛, 刘婧. 基于复杂软件网络的回归测试用例优先级排序[J]. 电子学报, 2012, 40(12): 2456-2465.
[13]	张健沛, 李泓波, 杨静, 白劲波, 张乐君, 初妍. 基于归属不确定性的变规模网络重叠社区识别[J]. 电子学报, 2012, 40(12): 2512-2518.
[14]	汤进;陈展展;罗斌;孙登第. 基于复杂网络和最优子序列双射的形状描述与匹配[J]. 电子学报, 2011, 39(8): 1757-1765.
[15]	金弟;刘大有;杨博;刘杰;何东晓;田野. 基于局部探测的快速复杂网络聚类算法[J]. 电子学报, 2011, 39(11): 2540-2546.