-
复杂网络中节点重要性的评估是网络特性研究中的一项重要课题, 相关研究具有广泛的应用. 目前提出了许多方法来评估网络中节点的重要性, 然而大多数方法都存在评估角度片面或者时间复杂度过高的不足. 为了突破现有方法的局限性, 本文提出了一种. 该方法兼顾节点的局部和全局拓扑信息, 综合考察节点的结构洞特征和K壳中心性, 并充分考虑节点及其邻域节点的影响. 为了验证该方法的有效性, 本文采用单调性指标、SIR模型和Kendall相关系数作为评价标准, 在8个来自不同领域的真实网络上与其他方法进行比较. 实验结果表明, 此方法能更有效和准确地评估网络节点的重要性, 可以显著区分不同节点的重要性. 此外, 该方法的时间复杂度仅为
$ O({n^2}) $ , 适用于大型复杂网络.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
下载:
导出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}) $ 下载:
导出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 下载:
导出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 下载:
导出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 下载:
导出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 下载:
导出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] 汪亭亭, 梁宗文, 张若曦.基于信息熵与迭代因子的复杂网络节点重要性评价方法. 必威体育下载 , 2023, 72(4): 048901.doi:10.7498/aps.72.20221878 [2] 丁慧强, 戴婷婷, 程鸾, 张卫宁, 王恩科.低横动量 $\varUpsilon(1 S)$ 介子在强子气体中的分布. 必威体育下载 , 2023, 72(19): 192501.doi:10.7498/aps.72.20230990[3] 刘慧, 王炳珺, 陆君安, 李增扬.复杂网络牵制控制优化选点算法及节点组重要性排序. 必威体育下载 , 2021, 70(5): 056401.doi:10.7498/aps.70.20200872 [4] 黄丽亚, 霍宥良, 王青, 成谢锋.基于K-阶结构熵的网络异构性研究. 必威体育下载 , 2019, 68(1): 018901.doi:10.7498/aps.68.20181388 [5] 黄丽亚, 汤平川, 霍宥良, 郑义, 成谢锋.基于加权K-阶传播数的节点重要性. 必威体育下载 , 2019, 68(12): 128901.doi:10.7498/aps.68.20190087 [6] 马堃, 焦铮, 蒋峰建, 叶剑锋, 吕海江, 陈展斌.洞态Ar原子Kα和Kβ伴线和超伴线的理论计算. 必威体育下载 , 2018, 67(17): 173201.doi:10.7498/aps.67.20180553 [7] 杨剑楠, 刘建国, 郭强.基于层间相似性的时序网络节点重要性研究. 必威体育下载 , 2018, 67(4): 048901.doi:10.7498/aps.67.20172255 [8] 孔江涛, 黄健, 龚建兴, 李尔玉.基于复杂网络动力学模型的无向加权网络节点重要性评估. 必威体育下载 , 2018, 67(9): 098901.doi:10.7498/aps.67.20172295 [9] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋.基于领域相似度的复杂网络节点重要度评估算法. 必威体育下载 , 2017, 66(3): 038902.doi:10.7498/aps.66.038902 [10] 王雨, 郭进利.基于多重影响力矩阵的有向加权网络节点重要性评估方法. 必威体育下载 , 2017, 66(5): 050201.doi:10.7498/aps.66.050201 [11] 苏晓萍, 宋玉蓉.利用邻域“结构洞”寻找社会网络中最具影响力节点. 必威体育下载 , 2015, 64(2): 020101.doi:10.7498/aps.64.020101 [12] 韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰.面向结构洞的复杂网络关键节点排序. 必威体育下载 , 2015, 64(5): 058902.doi:10.7498/aps.64.058902 [13] 邹小翠, 吴木生, 刘刚, 欧阳楚英, 徐波.β-碳化硅/碳纳米管核壳结构的第一性原理研究. 必威体育下载 , 2013, 62(10): 107101.doi:10.7498/aps.62.107101 [14] 刘建国, 任卓明, 郭强, 汪秉宏.复杂网络中节点重要性排序的研究进展. 必威体育下载 , 2013, 62(17): 178901.doi:10.7498/aps.62.178901 [15] 任卓明, 邵凤, 刘建国, 郭强, 汪秉宏.基于度与集聚系数的网络节点重要性度量方法研究. 必威体育下载 , 2013, 62(12): 128901.doi:10.7498/aps.62.128901 [16] 于会, 刘尊, 李勇军.基于多属性决策的复杂网络节点重要性综合评价方法. 必威体育下载 , 2013, 62(2): 020204.doi:10.7498/aps.62.020204 [17] 唐英干, 邸秋艳, 赵立兴, 关新平, 刘福才.基于二维最小Tsallis交叉熵的图像阈值分割方法. 必威体育下载 , 2009, 58(1): 9-15.doi:10.7498/aps.58.9 [18] 康冬鹏, 任 珉, 马爱群, 钱 妍, 刘正君, 刘树田.k光子Jaynes-Cummings模型光场的熵压缩. 必威体育下载 , 2008, 57(2): 873-879.doi:10.7498/aps.57.873 [19] 廖伯琴, 林辛未.164Er96与166Er98核推转壳模型波函数的K结构新探. 必威体育下载 , 1991, 40(11): 1741-1748.doi:10.7498/aps.40.1741 [20] 彭桓武.寿命关联实验的重要性. 必威体育下载 , 1962, 18(3): 165-166.doi:10.7498/aps.18.165
下载:
计量
- 文章访问数:6558
- PDF下载量:190
- 被引次数:0