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

王环; 朱敏

doi:10.3969/j.issn.1000-5641.2019.03.011

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

doi: 10.3969/j.issn.1000-5641.2019.03.011

王环^1,,
朱敏^2, ,

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

详细信息

作者简介:
王环, 女, 硕士研究生, 研究方向为大数据分析与知识处理.E-mail:18788803206@163.com

通讯作者:
朱敏, 女, 教授级高级工程师, 硕士生导师, 研究方向为智能计算与智能系统、现代软件技术.E-mail:mzhu@cc.ecnu.edu.cn

中图分类号: TP391
计量
- 文章访问数: 75
- HTML全文浏览量: 22
- PDF下载量: 112
- 被引次数: 0
出版历程
- 收稿日期: 2018-04-09
- 刊出日期: 2019-05-25

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

WANG Huan^1
,,
ZHU Min^{2
, ,}

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

摘要

摘要: 复杂网络中，评估节点的重要性对于研究网络结构和传播过程有着重要意义.通过节点的位置，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.
- complex network /
- vital nodes /
- K-shell decomposition algorithm /
- weighted kernel value /
- degree index

HTML全文

图 1 示例网络图^[16], 图中节点1和节点16度数相同且最高为6, 但节点1位于网络中心位置, 节点16位于网络的边缘位置; $K$-shell分解算法根据节点的位置有效地判断节点的重要性, 但不能很好地区分相同$K$s值节点的重要性

Fig. 1 In an example network, nodes 1 and 16 have the highest degree; node 1 is at the core of the network, while node 16 is located at the edge of the network; the $K$-shell decomposition algorithm can judge the importance of a node based on its position effectively, but the importance of nodes with the same $K$s value cannot be distinguished well

下载: 全尺寸图片幻灯片

图 2 种网络的排名分布情况(CDF图像)

Fig. 2 Distribution of ranks in four real networks (via graph of the cumulative distribution function)

下载: 全尺寸图片幻灯片

图 3 不同感染概率下, 各算法排序结果与SIR模型产生排序结果的肯德尔系数值$\tau $

Fig. 3 The Kendall coefficient value ($\tau $) of the ranking result produced by each algorithm and the SIR model with different infection probabilities

下载: 全尺寸图片幻灯片

表 1 不同算法排序结果

Tab. 1 Sorting results using different algorithms

排名	DC	$K$s	MDD	w$K$s	C$_{\mathrm {nc}^+}$	EL$K$SS	E$K$SDN
1	1, 16	1, 2, 3, 4	1, 16	1	1, 2	1	1
2	2, 4	5, 11, 12, 13	2, 4	2	4	2	4
3	3, 5, 13	others	3	4, 16	3	4	2
4	22		5, 13	3	13	3	3
5	6, 8, 11, 12, 21		22	5	5	16	16
6	others		11, 12, 21	13	11, 12	5	5
7			6, 8	11, 12, 21, 22	16	13	13
8			others	6, 8	10	11, 12	11, 12
9				17, 18, 19, 20	21	6, 8, 21	10
10				10, 14, 15	6, 8	10	21
11				7, 9, 23, 24	14, 15, 17, 18, 19, 20	14, 15	6, 8
12					22	17, 18, 19, 20	17, 18, 19, 20
13					7, 9, 23, 24	22	22
14						7, 9	14, 15
15						23, 24	7, 9
16							23, 24

下载: 导出CSV

表 2 网络统计特性

Tab. 2 Network statistics

网络	$N$	$E$	$k$	$\beta _{\rm th} $	$C$	$d$
Karate Club	34	78	4.58	0.129	0.571	2.41
NetScience	379	914	4.82	0.125	0.741	6.04
Email	1 133	5 451	9.62	0.054	0.221	3.61
Blogs	1 222	16 714	27.35	0.072	0.284	6.25

下载: 导出CSV

表 3 单调性指标

Tab. 3 Monotonicity index

算法	Karate Club	Email	NetScience	Blogs
DC	0.707 9	0.887 4	0.764 2	0.565 4
$K$s	0.495 8	0.808 8	0.642 1	0.467 0
MDD	0.753 6	0.922 9	0.821 5	0.590 6
w$K$s	0.687 8	0.920 1	0.824 1	0.603 2
C$_{\mathrm {nc}^+}$	0.947 2	0.999 1	0.989 3	0.986 8
E$K$SDN	0.954 2	0.999 9	0.994 9	0.997 5

下载: 导出CSV

参考文献(24)

[1]	LAWYER G. Understanding the influence of all nodes in a network[J]. Scientific Reports, 2015(5):8665. http://cn.bing.com/academic/profile?id=e7c21c2169af0ea3a66207f777561428&encoded=0&v=paper_preview&mkt=zh-cn
[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. doi: 10.1016/j.physrep.2016.06.007
[3]	BONACICH P. Factoring and weighting approaches to status scores and clique identification[J]. Journal of Mathematical Sociology, 1972, 2(1):113-120. doi: 10.1080/0022250X.1972.9989806
[4]	FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1):35-41. doi: 10.2307/3033543
[5]	BONACICH P. Some unique properties of eigenvector centrality[J]. Social Networks, 2007, 29(4):555-564. doi: 10.1016/j.socnet.2007.04.002
[6]	LATORA V, MARCHIORI M. Efficient behavior of small-world networks.[J]. Physical Review Letters, 2001, 87(19):198701. doi: 10.1103/PhysRevLett.87.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. https://www.researchgate.net/publication/221520147_Twitterrank_Finding_Topic-Sensitive_Influential_Twitterers
[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. doi: 10.1073/pnas.0507655102
[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. doi: 10.1016/S0378-8733(00)00020-4
[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. doi: 10.1016/j.physa.2011.09.017
[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. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=79a0a98ee340d21279980118f457b75f
[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. doi: 10.1038/nphys1746
[13]	ZENG A, ZHANG C J. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013, 377(14):1031-1035. doi: 10.1016/j.physleta.2013.02.039
[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. doi: 10.1016/j.physa.2014.11.012
[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. http://cn.bing.com/academic/profile?id=c14c8e5086ed4bc2d471c0bd0cc6f9b7&encoded=0&v=paper_preview&mkt=zh-cn
[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. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=10.1142_S0129183117500140
[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. http://cn.bing.com/academic/profile?id=286343aa8d0c77f9cf804f53a24d2222&encoded=0&v=paper_preview&mkt=zh-cn
[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. doi: 10.1086/jar.33.4.3629752
[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. doi: 10.1103-PhysRevE.74.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. doi: 10.1080/15427951.2009.10129177
[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. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=5cc1ed38f83482c3bd9bf300964ad34d
[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. http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_cond-mat%2f0205009
[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. doi: 10.1007/s11071-011-9984-7