华东师范大学学报（自然科学版） >

2019 , Vol. 2019 >Issue 3: 101 - 109

DOI: https://doi.org/10.3969/j.issn.1000-5641.2019.03.011

计算机科学

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

  • 王环 ,
  • 朱敏
展开
  • 1. 华东师范大学 计算机科学技术系, 上海 200062;
    2. 华东师范大学 计算中心, 上海 200062
王环,女,硕士研究生,研究方向为大数据分析与知识处理.E-mail:18788803206@163.com.

收稿日期: 2018-04-09

  网络出版日期: 2019-05-30

收起

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

  • WANG Huan ,
  • ZHU Min
Expand
  • 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 date: 2018-04-09

  Online published: 2019-05-30

Fold

摘要

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

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

本文引用格式

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

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

参考文献

[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.
Options
文章导航

/

〈 〉