-
Evaluating the importance of nodes in complex networks is an important topic in the research of network characteristics. Its relevant research has a wide range of applications, such as network supervision and rumor control. At present, many methods have been proposed to evaluate the importance of nodes in complex networks, but most of them have the deficiency of one-sided evaluation or too high time complexity. In order to break through the limitations of existing methods, in this paper a novel method of evaluating the importance of complex network nodes is proposed based on Tsallis entropy. This method takes into account both the local and global topological information of the node. It considers the structural hole characteristics and K-shell centrality of the node and fully takes into account the influence of the node itself and its neighboring nodes. To illustrate the effectiveness and applicability of this method, eight real networks are selected from different fields and five existing methods of evaluating node importance are used as comparison methods. On this basis, the monotonicity index, SIR (susceptible-infectious-recovered) model, and Kendall correlation coefficient are used to illustrate the superiority of this method and the relationship among different methods. Experimental results show that this method can effectively and accurately evaluate the importance of nodes in complex networks, distinguish the importance of different nodes significantly, and can show good accuracy of evaluating the node importance under different proportions of nodes. In addition, the time complexity of this method is
$ O({n^2}) $ , which is suitable for large-scale complex networks.-
Keywords:
- node importance/
- Tsallis entropy/
- structural hole/
- K-shell
[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] -
Algorithm 1:TSM algorithm. Input: Network $ G(V, E) $
Output: TSM value for each node
1. Find neighboring nodes $\varGamma (i)$of node $ {v_i} $
2. Compute the restraint coefficient ${\rm{RC}}_i$ of node $ {v_i} $
3. Compute the ${\rm Ks}_i$ value of node $ {v_i} $according to formula $k_i^{\rm m} = k_i^{\rm r} + \lambda k_i^{\rm e}$
4. Compute $ {q_i} $ for node $ {v_i} $
5.Fornode $ {v_j} $ in $\varGamma (i)$ do
6. ratio = ($1 - {\rm{RC}}_j$)/${\rm{sum}}$($1 - {\rm{RC}}$(all neighbors of $ {v_i} $))
7. $ T({v_i}) $= (pow(ratio, $ {q_i} $)-ratio)/(1 – $ {q_i} $)
8.End For
9. Compute ${\rm{IC} }\left( { {v_i} } \right) = \left( {1 - {\rm{RC} }_i } \right)*T\left( { {v_i} } \right)$
10.Fornode $ {v_j} $ in $\varGamma (i)$ do
11. ${\rm{Cnc}}\left( { {v_i} } \right) = {\rm{sum}}\left( {{\rm{IC}}\left( { {v_j} } \right)} \right)$
12.End For
13.Fornode $ {v_j} $ in $\varGamma (i)$ do
14. ${\rm{TSM}}\left( { {v_i} } \right) = {\rm{sum}}\left( {{\rm{Cnc}}\left( { {v_j} } \right)} \right)$
15.End For
DownLoad:
CSV
Method Category Time complexity $ {\text{DC}} $ Local $ O(n) $ $ {\text{BC}} $ Global $ O({n^3}) $or$ O(nm) $ $ {\text{MDD}} $ Global $ O(n) $ ${\text{N-Burt} }$ Local $ O({n^2}) $ $ {\text{Cnc + }} $ Hybrid $ O(n) $ $ {\text{AAD}} $ Hybrid $ O({n^3}) $ or $ O(nm) $ $ {\text{IKS}} $ Hybrid $ O(n) $ $ {\text{TSM}} $ Hybrid $ O({n^2}) $ DownLoad:
CSV
Network $ n $ $ m $ $\langle k \rangle$ $ c $ $\langle d \rangle$ ${\beta _{\rm th} }$ $\beta $ Karate 34 78 4.5880 0.5706 2.4082 0.1287 0.25 Dolphins 62 159 5.1290 0.2590 3.3570 0.1470 0.15 Polbooks 105 441 8.4000 0.4880 3.0788 0.0838 0.10 Jazz 198 2742 27.6970 0.6175 2.2350 0.0259 0.04 USAir 332 2126 12.8072 0.7494 2.7381 0.0225 0.03 C.Elegans 453 2025 8.9404 0.6465 2.4553 0.0249 0.03 Email 1133 5451 9.6222 0.2540 3.6060 0.0535 0.05 PowerGrid 4941 6594 2.6691 0.0801 18.9892 0.2583 0.25 DownLoad:
CSV
排名 节点 DC 节点 BC 节点 MDD 节点 N-Burt 节点 Cnc+ 节点 AAD 节点 IKS 节点 TSM 1 ${v_{34}}$ 17 ${v_1}$ 0.4119 ${v_{34}}$ 11.9 ${v_{34}}$ 0.1682 ${v_{34}}$ 1156 ${v_{34}}$ 17.4666 ${v_1}$ 1.5215 ${v_{34}}$ 89.8687 2 ${v_1}$ 16 ${v_{34}}$ 0.2862 ${v_1}$ 11.2 ${v_1}$ 0.1731 ${v_1}$ 1024 ${v_1}$ 16.4976 ${v_{34}}$ 1.4782 ${v_1}$ 81.8535 3 ${v_{33}}$ 12 ${v_{33}}$ 0.1367 ${v_{33}}$ 8.7 ${v_3}$ 0.2257 ${v_{33}}$ 576 ${v_{33}}$ 12.6498 ${v_3}$ 1.2610 ${v_{33}}$ 72.0759 4 ${v_3}$ 10 ${v_3}$ 0.1352 ${v_3}$ 7.6 ${v_{33}}$ 0.2746 ${v_3}$ 400 ${v_3}$ 10.7712 ${v_{33}}$ 1.2307 ${v_3}$ 70.7235 5 ${v_2}$ 9 ${v_{32}}$ 0.1301 ${v_2}$ 6.9 ${v_{32}}$ 0.2793 ${v_2}$ 324 ${v_2}$ 9.8490 ${v_2}$ 1.0208 ${v_2}$ 59.4435 6 ${v_4}$ 6 ${v_9}$ 0.0526 ${v_4}$ 5.1 ${v_9}$ 0.3266 ${v_4}$ 144 ${v_4}$ 7.2111 ${v_9}$ 0.9425 ${v_9}$ 47.6431 7 ${v_{32}}$ 6 ${v_2}$ 0.0508 ${v_{32}}$ 5.1 ${v_2}$ 0.3357 ${v_{32}}$ 108 ${v_{32}}$ 6.7095 ${v_{14}}$ 0.9411 ${v_{14}}$ 46.9374 8 ${v_9}$ 5 ${v_{14}}$ 0.0432 ${v_{14}}$ 5 ${v_{14}}$ 0.3541 ${v_9}$ 100 ${v_9}$ 6.4033 ${v_{32}}$ 0.9004 ${v_4}$ 45.5295 9 ${v_{14}}$ 5 ${v_{20}}$ 0.0306 ${v_9}$ 4.7 ${v_{28}}$ 0.3674 ${v_{14}}$ 100 ${v_{14}}$ 6.4033 ${v_4}$ 0.8343 ${v_{32}}$ 41.3938 10 ${v_{24}}$ 5 ${v_6}$ 0.0282 ${v_{24}}$ 4.1 ${v_{31}}$ 0.3810 ${v_{24}}$ 75 ${v_{24}}$ 5.8310 ${v_{31}}$ 0.7137 ${v_{31}}$ 37.1209 11 ${v_6}$ 4 ${v_7}$ 0.0282 ${v_8}$ 4 ${v_{20}}$ 0.3935 ${v_8}$ 64 ${v_{31}}$ 5.6569 ${v_{24}}$ 0.7027 ${v_8}$ 35.7453 12 ${v_7}$ 4 ${v_{28}}$ 0.0210 ${v_{31}}$ 4 ${v_{29}}$ 0.4115 ${v_{31}}$ 64 ${v_8}$ 5.6569 ${v_8}$ 0.6996 ${v_{24}}$ 33.3428 13 ${v_8}$ 4 ${v_{24}}$ 0.0166 ${v_{28}}$ 3.7 ${v_{24}}$ 0.4348 ${v_6}$ 48 ${v_6}$ 5.0001 ${v_{20}}$ 0.6397 ${v_{28}}$ 29.9028 14 ${v_{28}}$ 4 ${v_{31}}$ 0.0136 ${v_{30}}$ 3.7 ${v_4}$ 0.4684 ${v_7}$ 48 ${v_7}$ 5.0001 ${v_{30}}$ 0.6050 ${v_{20}}$ 29.6927 15 ${v_{30}}$ 4 ${v_4}$ 0.0112 ${v_6}$ 3.4 ${v_{26}}$ 0.4845 ${v_{28}}$ 48 ${v_{28}}$ 5.0000 ${v_{28}}$ 0.6039 ${v_{30}}$ 29.1552 DownLoad:
CSV
Network $ M{\text{(DC)}} $ M(BC) M(MDD) $M{\text{(N-Burt)} }$ $ M{\text{(Cnc + )}} $ M(ADD) $ M{\text{(IKS)}} $ $ M{\text{(TSM)}} $ Karate 0.7079 0.7723 0.7536 0.9542 0.9472 0.8395 0.9612 0.9542 Dolphins 0.8312 0.9623 0.9041 0.9623 0.9895 0.9623 0.9905 0.9979 Polbooks 0.8252 0.9974 0.9077 1 0.9971 0.9996 1 1 Jazz 0.9659 0.9885 0.9883 0.9983 0.9993 0.9981 0.9994 0.9994 USAir 0.8586 0.6970 0.8871 0.9453 0.9945 0.9068 0.9943 0.9951 C.Elegans 0.7922 0.8740 0.8748 0.9983 0.9980 0.9381 0.9974 0.9990 Email 0.8874 0.9400 0.9229 0.9650 0.9991 0.9629 0.9995 0.9999 PowerGrid 0.5927 0.8313 0.6928 0.8770 0.9568 0.8748 0.9667 0.9999 DownLoad:
CSV
Network $\tau ({\text{DC, }}\sigma {\text{)}}$ $\tau ({\text{BC, }}\sigma {\text{)}}$ $\tau ({\text{MDD, }}\sigma {\text{)}}$ $\tau ({\text{N-Burt, } }\sigma {\text{)} }$ $\tau ({\text{Cnc + , }}\sigma {\text{)}}$ $\tau ({\text{AAD, }}\sigma {\text{)}}$ $\tau ({\text{IKS, }}\sigma {\text{)}}$ $\tau ({\text{TSM, }}\sigma {\text{)}}$ Karate 0.6435 0.5651 0.6756 0.7683 0.9258 0.6591 0.8445 0.9637 Dolphins 0.7768 0.5643 0.8181 0.7282 0.8611 0.7532 0.8526 0.9492 Polbooks 0.7528 0.3579 0.8029 0.7037 0.9098 0.7691 0.9165 0.9436 Jazz 0.8185 0.4628 0.8503 0.8216 0.9132 0.8235 0.8804 0.9363 USAir 0.6982 0.4744 0.7175 0.7929 0.9047 0.6995 0.9055 0.9461 C.Elegans 0.6376 0.4711 0.6521 0.6251 0.8127 0.659 0.8217 0.8570 Email 0.7911 0.6467 0.8015 0.7735 0.8980 0.7797 0.8758 0.9250 PowerGrid 0.5469 0.4167 0.5786 0.4298 0.7341 0.5563 0.7399 0.8207 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] -
[1] Wang Ting-Ting, Liang Zong-Wen, Zhang Ruo-Xi.Importance evaluation method of complex network nodes based on information entropy and iteration factor. Acta Physica Sinica, 2023, 72(4): 048901.doi:10.7498/aps.72.20221878 [2] Ding Hui-Qiang, Dai Ting-Ting, Cheng Luan, Zhang Wei-Ning, Wang En-Ke.Distribution of low- $p_{\rm{T}}$ $\varUpsilon(1 S)$ in hadron gas. Acta Physica Sinica, 2023, 72(19): 192501.doi:10.7498/aps.72.20230990[3] Liu Hui, Wang Bing-Jun, Lu Jun-An, Li Zeng-Yang.Node-set importance and optimization algorithm of nodes selection in complex networks based on pinning control. Acta Physica Sinica, 2021, 70(5): 056401.doi:10.7498/aps.70.20200872 [4] Huang Li-Ya, Huo You-Liang, Wang Qing, Cheng Xie-Feng.Network heterogeneity based onK-order structure entropy. Acta Physica Sinica, 2019, 68(1): 018901.doi:10.7498/aps.68.20181388 [5] Huang Li-Ya, Tang Ping-Chuan, Huo You-Liang, Zheng Yi, Cheng Xie-Feng.Node importance based on the weightedK-order propagation number algorithm. Acta Physica Sinica, 2019, 68(12): 128901.doi:10.7498/aps.68.20190087 [6] Ma Kun, Jiao Zheng, Jiang Feng-Jian, Ye Jian-Feng, Lv Hai-Jiang, Chen Zhan-Bin.Theoretical calculation of Kα and Kβ X-ray satellite and hypersatellite structures for hollow argon atoms. Acta Physica Sinica, 2018, 67(17): 173201.doi:10.7498/aps.67.20180553 [7] Yang Jian-Nan, Liu Jian-Guo, Guo Qiang.Node importance idenfication for temporal network based on inter-layer similarity. Acta Physica Sinica, 2018, 67(4): 048901.doi:10.7498/aps.67.20172255 [8] 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 [9] 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 [10] Wang Yu, Guo Jin-Li.Evaluation method of node importance in directed-weighted complex network based on multiple influence matrix. Acta Physica Sinica, 2017, 66(5): 050201.doi:10.7498/aps.66.050201 [11] Su Xiao-Ping, Song Yu-Rong.Leveraging neighborhood “structural holes” to identifying key spreaders in social networks. Acta Physica Sinica, 2015, 64(2): 020101.doi:10.7498/aps.64.020101 [12] 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 [13] Zou Xiao-Cui, Wu Mu-Sheng, Liu Gang, Ouyang Chu-Ying, Xu Bo.First-principles study on the electronic structures of β-SiC/carbon nanotube core-shell structures. Acta Physica Sinica, 2013, 62(10): 107101.doi:10.7498/aps.62.107101 [14] 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 [15] Ren Zhuo-Ming, Shao Feng, Liu Jian-Guo, Guo Qiang, Wang Bing-Hong.Node importance measurement based on the degree and clustering coefficient information. Acta Physica Sinica, 2013, 62(12): 128901.doi:10.7498/aps.62.128901 [16] 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 [17] Tang Ying-Gan, Di Qiu-Yan, Zhao Li-Xing, Guan Xin-Ping, Liu Fu-Cai.Image thresholding segmentation based on two-dimensional minimum Tsallis-cross entropy. Acta Physica Sinica, 2009, 58(1): 9-15.doi:10.7498/aps.58.9 [18] Kang Dong-Peng, Ren Min, Ma Ai-Qun, Qian Yan, Liu Zheng-Jun, Liu Shu-Tian.Entropy squeezing of the optical field in k-photon Jaynes-Cummings model. Acta Physica Sinica, 2008, 57(2): 873-879.doi:10.7498/aps.57.873 [19] LIAO BO-QIN, LIN XIN-WEI.K-STRUCTURES OF THE CSM WAVE FUNCTIONS OF 164Er96 AND 166Er98. Acta Physica Sinica, 1991, 40(11): 1741-1748.doi:10.7498/aps.40.1741 [20] PENG HWAN-WU.IMPORTANCE OF LIFE TIME CORRELATION EXPERIMENTS. Acta Physica Sinica, 1962, 18(3): 165-166.doi:10.7498/aps.18.165
DownLoad:
Catalog
Metrics
- Abstract views:6583
- PDF Downloads:191
- Cited By:0