Importance evaluation method of complex network nodes based on information entropy and iteration factor

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

Abstract

In the study of complex networks, researchers have long focused on the identification of influencing nodes. Based on topological information, several quantitative methods of determining the importance of nodes are proposed. K-shell is an efficient way to find potentially affected nodes. However, the K-shell overemphasizes the influence of the location of the central nodebut ignores the effect of the force of the nodes located at the periphery of the network. Furthermore, the topology of real networks is complex, which makes the computation of the K-shell problem for large scale-free networks extremely difficult. In order to avoid ignoring the contribution of any node in the network to the propagation, this work proposes an improved method based on the iteration factor and information entropy to estimate the propagation capability of each layer of nodes. This method not only achieves the accuracy of node ordering, but also effectively avoids the phenomenon of rich clubs. To evaluate the performance of this method, the SIR model is used to simulate the propagation efficiency of each node, and the algorithm is compared with other algorithms. Experimental results show that this method has better performance than other methods and is suitable for large-scale networks.

Keywords:

Authors and contacts

Corresponding author:Liang Zong-Wen,zongwen-liang@hotmail.com

FullText HTML: translate this paragraph

References

[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
[32]
[33]
[34]
[35]
[36]
[37]
[38]
[39]
[40]
[41]
[42]
[43]
[44]
[45]
[46]

Cited By

DownLoad: Full-Size Img PowerPoint

ks	Node	E
3	1	0.9571
	4	0.8565
	5	0.8099
	2	0.7151
	3	0.6366
2	7/8/9	0.4861
2	6	0.4374
1	21	0.6675
	10	0.4034
	23	0.3720
	20/22/24/25/26	0.2420
	11/12/13/14/16	0.1992
	15	0.1733
	17/18/19	0.1435

DownLoad: CSV

Iteration	Node	E₊
7	5	1.3728
6	1	1.4579
	4	1.4378
	2	1.2159
	3	1.0589
5	7/8	0.7839
4	6	0.7189
4	9	0.6430
3	21	0.8084
2	10	0.4818
2	23	0.3720
1	16	0.3400
	15	0.3139
	20/22/24/25/26	0.2420
	17	0.2219
	11/12/13/14	0.1992
	18/19	0.1435

DownLoad: CSV

IE₊算法伪代码
输入: 网络结构G=(V,E)
输出: 网络中节点的排序索引Rank
1: 通过G= (V,E)得出邻接矩阵A
2: 通过K-shell算法得出每个节点的ks值
3: IT ← 1
4: while \|V\| do
5:V_temp←{ }
6:V_i.k← $\displaystyle\sum\nolimits_{j = 1}^N { {a_{ij} } }$
7: mindegree ← min(V.k)
8: V_temp← find (V.k== mindegree)
9: whileV_tempdo
10: V_temp. IT←IT
11:V_temp.e₊←$ -{\sum }_{j\in \varGamma \left(i\right)}{I}_{j}\cdot {\rm{ln}}{I}_{j}\cdot {\rm{k}}{{\rm{s}}}_{j} $
12: endwhile
13: delete(V_temp)
14: IT←IT+1
15:V←V-V_temp
16: endwhile
17: ITMax ← IT
18: while length(Rank) <Ndo
19: for IT←ITMax to 1 do
20:V_temp= find(max(V.IT.e₊))
21: if length (V_temp) > 1
22: 按节点序号从大到小排序
23: end if
24: Rank ← {V_temp, Rank}
25: end for
26: end while
27: return Rank

DownLoad: CSV

Rank	DC	CC	ks	C_nc	C_nc+	IKS	IE₊
1	21	1	1—5	4, 5	1	1	5
2	1, 4, 5, 10	4	6—9	1	4, 5	7	1
3	2, 3	5	10—26	2	2	21	8
4	6—9, 23	21		3	3	4	7
5	11—20	7, 8		21	6—8	9	6
6	22, 24—26	6		6—8	9, 21	10	21
7		9		10	16	5	10
8		23		9	23	8	16
9		16, 20, 22, 24—26		15, 16, 23	15	23	4
10				17	10, 20, 22, 24—26	2	9
11				others		6	23
12						26	15
13						3	2
14						20, 22, 24, 25	20, 22, 24—262
15						11—13, 14, 16	3
16						15	17
17						17—19	11—14
18							18, 19

DownLoad: CSV

Network	N	\|E\|	$\langle d \rangle$	c	$ \langle k \rangle $	β_th	β_c
NS	379	914	6.0419	0.7981	4.8232	0.1247	0.2494
EEC	986	16064	2.5869	0.4505	32.5842	0.0134	0.0268
PB	1222	16714	2.7375	0.3600	27.3552	0.0123	0.0246
Fecebook	4039	88234	3.6925	0.6170	43.6910	0.0094	0.0188
WV	7066	100736	3.2475	0.2090	28.5129	0.0069	0.0138
Sport	13866	86858	4.2748	0.2761	12.5281	0.0260	0.0520
Sex	15810	38540	7.4630	0	4.8754	0.0365	0.0730
CondMat	23122	93497	5.3523	0.6334	8.0835	0.0450	0.0900

DownLoad: CSV

Network	DC	CC	C_nc	C_nc+	ks	IKS	IE₊
NS	0.4593	0.3829	0.5604	0.7074	0.4643	0.7301	0.8958
EEC	0.8584	0.8238	0.8999	0.8771	0.8754	0.8963	0.9017
PB	0.8443	0.7956	0.8771	0.8667	0.8653	0.8859	0.9465
Facebook	0.6255	0.4948	0.7416	0.8614	0.6773	0.8926	0.9364
WV	0.8022	0.8583	0.8992	0.8939	0.9171	0.8981	0.9661
Sport	0.6909	0.6891	0.7875	0.8025	0.7437	0.8583	0.9197
Sex	0.4119	0.7329	0.7623	0.8283	0.5151	0.8065	0.8174
CondMat	0.5912	0.7268	0.7303	0.8114	0.6464	0.8565	0.9254

DownLoad: CSV

Network	M(DC)	M(CC)	M(C_nc)	M(C_nc+)	M(ks)	M(IKS)	M(IE₊)
NS	0.7642	0.9927	0.9302	0.9593	0.6428	0.8286	0.9221
EEC	0.9571	0.9828	0.9748	0.9998	0.9216	0.9328	0.9881
PB	0.9328	0.9301	0.9433	0.9586	0.9063	0.9266	0.9721
Facebook	0.9398	0.9667	0.9355	0.9646	0.9419	0.9457	0.9898
Sport	0.9032	0.9534	0.9292	0.9377	0.8606	0.9137	0.9818
Sex	0.6001	0.9122	0.9332	0.9581	0.5287	0.9248	0.9989
CondMat	0.8615	0.9544	0.9871	0.9864	0.8032	0.9069	0.9996

DownLoad: CSV

[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
[32]
[33]
[34]
[35]
[36]
[37]
[38]
[39]
[40]
[41]
[42]
[43]
[44]
[45]
[46]

[1]	Ruan Yi-Run, Lao Song-Yang, Tang Jun, Bai Liang, Guo Yan-Ming.Node importance ranking method in complex network based on gravity method. Acta Physica Sinica, 2022, 71(17): 176401.doi:10.7498/aps.71.20220565
[2]	Ma Jin-Long, Zhang Jun-Feng, Zhang Dong-Wen, Zhang Hong-Bin.Quantifying complex network traffic capacity based on communicability sequence entropy. Acta Physica Sinica, 2021, 70(7): 078902.doi:10.7498/aps.70.20201300
[3]	Chen Dan, Shi Dan-Dan, Pan Gui-Jun.Correlation between the electrical transport performance and the communicability sequence entropy in complex networks. Acta Physica Sinica, 2019, 68(11): 118901.doi:10.7498/aps.68.20190230
[4]	Kong Jiang-Tao, Huang Jian, Gong Jian-Xing, Li Er-Yu.Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models. Acta Physica Sinica, 2018, 67(9): 098901.doi:10.7498/aps.67.20172295
[5]	Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Hou Lü-Lin.An improved evaluating method of node spreading influence in complex network based on information spreading probability. Acta Physica Sinica, 2017, 66(20): 208901.doi:10.7498/aps.66.208901
[6]	Su Zhen, Gao Chao, Li Xiang-Hua.Analysis of the effect of node centrality on diffusion mode in complex networks. Acta Physica Sinica, 2017, 66(12): 120201.doi:10.7498/aps.66.120201
[7]	Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong.Node importance measurement based on neighborhood similarity in complex network. Acta Physica Sinica, 2017, 66(3): 038902.doi:10.7498/aps.66.038902
[8]	Han Zhong-Ming, Chen Yan, Li Meng-Qi, Liu Wen, Yang Wei-Jie.An efficient node influence metric based on triangle in complex networks. Acta Physica Sinica, 2016, 65(16): 168901.doi:10.7498/aps.65.168901
[9]	Han Zhong-Ming, Wu Yang, Tan Xu-Sheng, Duan Da-Gao, Yang Wei-Jie.Ranking key nodes in complex networks by considering structural holes. Acta Physica Sinica, 2015, 64(5): 058902.doi:10.7498/aps.64.058902
[10]	Duan Dong-Li, Zhan Ren-Jun.Evolution mechanism of node importance based on the information about cascading failures in complex networks. Acta Physica Sinica, 2014, 63(6): 068902.doi:10.7498/aps.63.068902
[11]	Ren Zhuo-Ming, Liu Jian-Guo, Shao Feng, Hu Zhao-Long, Guo Qiang.Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks. Acta Physica Sinica, 2013, 62(10): 108902.doi:10.7498/aps.62.108902
[12]	Liu Jin-Liang.Research on synchronization of complex networks with random nodes. Acta Physica Sinica, 2013, 62(4): 040503.doi:10.7498/aps.62.040503
[13]	Liu Jian-Guo, Ren Zhuo-Ming, Guo Qiang, Wang Bing-Hong.Node importance ranking of complex networks. Acta Physica Sinica, 2013, 62(17): 178901.doi:10.7498/aps.62.178901
[14]	Yu Hui, Liu Zun, Li Yong-Jun.Key nodes in complex networks identified by multi-attribute decision-making method. Acta Physica Sinica, 2013, 62(2): 020204.doi:10.7498/aps.62.020204
[15]	Zhou Xuan, Zhang Feng-Ming, Zhou Wei-Ping, Zou Wei, Yang Fan.Evaluating complex network functional robustness by node efficiency. Acta Physica Sinica, 2012, 61(19): 190201.doi:10.7498/aps.61.190201
[16]	LÜ Ling, Liu Shuang, Zhang Xin, Zhu Jia-Bo, Shen Na, Shang Jin-Yu.Spatiotemporal chaos anti-synchronization of a complex network with different nodes. Acta Physica Sinica, 2012, 61(9): 090504.doi:10.7498/aps.61.090504
[17]	Zhou Xuan, Zhang Feng-Ming, Li Ke-Wu, Hui Xiao-Bin, Wu Hu-Sheng.Finding vital node by node importance evaluation matrix in complex networks. Acta Physica Sinica, 2012, 61(5): 050201.doi:10.7498/aps.61.050201
[18]	Lü Ling, Zhang Chao.Chaos synchronization of a complex network with different nodes. Acta Physica Sinica, 2009, 58(3): 1462-1466.doi:10.7498/aps.58.1462
[19]	.Analysis of functional brain network based on electroencephalogram. Acta Physica Sinica, 2007, 56(12): 7330-7338.doi:10.7498/aps.56.7330
[20]	Li Ji, Wang Bing-Hong, Jiang Pin-Qun, Zhou Tao, Wang Wen-Xu.Growing complex network model with acceleratingly increasing number of nodes. Acta Physica Sinica, 2006, 55(8): 4051-4057.doi:10.7498/aps.55.4051

Catalog

Vol. 72, Issue 4 - 2023-02-20

Metrics

Abstract views:4097
PDF Downloads:154
Cited By:0

Search

Article