基于点权的混合K-shell关键节点识别方法

doi:10.3969/j.issn.1000-5641.2019.03.011

华东师范大学学报(自然科学版) ›› 2019, Vol. 2019 ›› Issue (3): 101-109.doi: 10.3969/j.issn.1000-5641.2019.03.011

基于点权的混合K-shell关键节点识别方法

王环¹, 朱敏²

1. 华东师范大学计算机科学技术系, 上海 200062;
2. 华东师范大学计算中心, 上海 200062

收稿日期:2018-04-09 出版日期:2019-05-25 发布日期:2019-05-30
通讯作者: 朱敏,女,教授级高级工程师,硕士生导师,研究方向为智能计算与智能系统、现代软件技术.E-mail:mzhu@cc.ecnu.edu.cn. E-mail:mzhu@cc.ecnu.edu.cn
作者简介:王环,女,硕士研究生,研究方向为大数据分析与知识处理.E-mail:18788803206@163.com.

Vital nodes identification by the hybrid K-shell method based on vertex strength

WANG Huan¹, ZHU Min²

1. Department of Computer Science and Technology, East China Normal University, Shanghai 200062, China;
2. The Computer Center, East China Normal University, Shanghai 200062, China

Received:2018-04-09 Online:2019-05-25 Published:2019-05-30

摘要/Abstract

摘要： 复杂网络中，评估节点的重要性对于研究网络结构和传播过程有着重要意义.通过节点的位置，K-shell分解算法能够很好地识别关键节点，但是这种算法导致很多节点具有相同的K-shell（Ks）值.同时，现有的算法大都只考虑局部指标或者全局指标，导致评判节点重要性的因素单一.为了更好地识别关键节点，提出了EKSDN（Extended K-shell and Degree of Neighbors）算法，该算法综合考虑了节点的全局指标加权核值以及节点的局部指标度数.与SIR（Susceptible-Infectious-Recovered）模型在真实复杂网络中模拟结果相比，EKSDN算法能够更好地识别关键节点.

关键词: 复杂网络, 关键节点, K-shell分解算法, 加权核值, 度指标

Abstract: In complex networks, evaluating the importance of individual nodes is of great significance to studying the structure of the network and the propagation process. Based on the location of nodes, the K-shell decomposition algorithm can identify key nodes well; however, it results in many nodes with the same K-shell (Ks) value. Meanwhile, most other algorithms only consider local or global indicators, which can lead to a single factor in judging the importance of a node. In order to better identify key nodes, we propose the extended K-shell and degree of neighbors (EKSDN) algorithm, which considers the global index weighted kernel value of the node and the local index degree of the node comprehensively. A comparison of our experimental results with results from the SIR (Susceptible-Infectious-Recovered) model on real complex networks, show that the proposed algorithm can better quantify the influence of a node.

Key words: complex network, vital nodes, K-shell decomposition algorithm, weighted kernel value, degree index

中图分类号:

TP391

王环, 朱敏. 基于点权的混合K-shell关键节点识别方法[J]. 华东师范大学学报(自然科学版), 2019, 2019(3): 101-109.

WANG Huan, ZHU Min. Vital nodes identification by the hybrid K-shell method based on vertex strength[J]. Journal of East China Normal University(Natural Sc, 2019, 2019(3): 101-109.

参考文献

[1] LAWYER G. Understanding the influence of all nodes in a network[J]. Scientific Reports, 2015(5):8665.
[2] LÜ L Y, CHEN D B, REN X L, et al. Vital nodes identification in complex networks[J]. Physics Reports, 2016, 650:1-63.
[3] BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology, 1972, 2(1):113-120.
[4] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1):35-41.
[5] BONACICH P. Some unique properties of eigenvector centrality[J]. Social Networks, 2007, 29(4):555-564.
[6] LATORA V, MARCHIORI M. Efficient behavior of small-world networks.[J]. Physical Review Letters, 2001, 87(19):198701.
[7] WENG J S, LIM E P, JIANG J, et al. TwitterRank:finding topic-sensitive influential twitterers[C]//Proceedings of the 3rd International Conference on Web Search and Web Data Mining, WSDM 2010. ACM, 2010:261-270.
[8] HIRSCH J E. An index to quantify an individual's scientific research output[J]. Proceedings of the National Academy of Sciences of the United States of America, 2005, 102(46):16569-16572.
[9] POULIN R, BOILY M C, MâSSE B R. Dynamical systems to define centrality in social networks[J]. Social Networks, 2000, 22(3):187-220.
[10] CHEN D B, LÜ L Y, SHANG M S, et al. Identifying influential nodes in complex networks[J]. Physica A:Statistical Mechanics and its Applications, 2012, 391(4):1777-1787.
[11] FEI L G, DENG Y. A new method to identify influential nodes based on relative entropy[J]. Chaos Solitons & Fractals, 2017, 104:257-267.
[12] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11):888-893.
[13] ZENG A, ZHANG C J. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013, 377(14):1031-1035.
[14] WEI B, LIU J, WEI D J, et al. Weighted k-shell decomposition for complex networks based on potential edge weights[J]. Physica A:Statistical Mechanics and its Applications, 2015, 420:277-283.
[15] 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(4):549-559.
[16] YANG F, ZHANG R S, YANG Z, et al. Identifying the most influential spreaders in complex networks by an Extended Local K-Shell Sum[J]. International Journal of Modern Physics C, 2017, 28(1):925-214.
[17] RUAN Y R,LAO S Y, XIAO Y D, et al. Identifying influence of nodes in complex networks with coreness centrality:Decreasing the impact of densely local connection[J]. Chinese Physics Letters, 2016, 33(2):149-152.
[18] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4):452-473.
[19] NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2006, 74(3 Pt 2):036104.
[20] LESKOVEC J, LANG K J, DASGUPTA A, et al. Community structure in large networks:Natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009, 6(1):29-123.
[21] 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.
[22] NWEMAN M E. Spread of epidemic disease on networks[J]. Physical Review E:Statistical Nonlinear & Soft Matter Physics, 2002, 66(1 Pt 2):016128.
[23] BALKEW T, MODEL S, RATE R R, et al. The SIR Model When S(t) is a Multi-Exponential Function[J]. Dissertations & Theses-Gradworks, 2010, 14(6):50-50.
[24] WANG X Y. An image blocks encryption algorithm based on spatiotemporal chaos[J]. Nonlinear Dynamics, 2012, 67(1):365-371.

基于点权的混合K-shell关键节点识别方法

Vital nodes identification by the hybrid K-shell method based on vertex strength

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	祁婷, 林诏华, 冯秘, 唐明. 复杂网络上非马尔科夫易感-感染模型的二阶平均场求解[J]. 华东师范大学学报（自然科学版）, 2021, 2021(1): 144-151.
[2]	李艺春, 孙慧, 姚兵. 几种可扩散网络模型的边魔幻偶优美性[J]. 华东师范大学学报(自然科学版), 2018, 2018(1): 11-16,23.
[3]	沈娉婷; 陈良育;. Java应用系统的复杂网络分析[J]. 华东师范大学学报(自然科学版), 2017, 2017(1): 38-51.