基于网络跨层信息熵的复杂网络节点重要性辨识
Node Importance Identification in Complex Networks Based on Multi-layer Iterative Information Entropy
-
摘要:
为解决经典K-shell分解算法范式化对复杂网络分层分级，导致网络层间层内节点辨识精细度降低等问题，提出一种网络跨层邻度（信息）熵算法。该算法首先改进K-shell分解算法分层过程，采用网络跨层中心性与网络跨层中心度以细化网络节点位置重要性；其次，综合分析网络跨层中心度、邻域中心性与信息熵中所包含的节点位置信息与邻居信息，采用网络跨层邻度熵算法对网络节点重要性进行辨识；最后，基于不同拓扑结构的5种网络，与其他算法分别就单调性、准确性及时间性能进行比较实验，实验结果表明，网络跨层邻度熵算法单调性最高可达
0.9999 ，精确性比其他算法最高提升21%。该算法具有更优越的网络节点辨识能力。Abstract:In order to solve the problem of reducing the precision of node identification between layers and within layers due to the hierarchical classification of complex networks by the classical K-shell decomposition algorithm, the network cross-layer adjacency entropy (multi-layer iterative information entropy) algorithm was proposed. Firstly, the decomposition process of K-shell decomposition algorithm was improved, and cross-layer centrality and cross-layer center degree of network were proposed to refine the importance of network node location. Secondly, the node location information and neighbor information contained in the network cross-layer centrality, neighborhood centrality and information entropy were analyzed comprehensively, and the network cross-layer adjacency entropy algorithm was proposed to identify the importance of network nodes. Finally, five kinds of networks with different topologies were compared with other algorithms in terms of monotonicity, accuracy and time performance. The experimental results show that the monotonicity of the cross-layer adjacency entropy algorithm is up to
0.9999 , and the accuracy is up to 21% higher than other algorithms, which indicates that the proposed algorithm has better ability to identify network nodes. -
随着复杂网络的发展，复杂网络关键节点辨识在航空网络[1 − 2]、国家电网[3 − 4]、交通网络[5 − 6]、社交网络[7 − 8]和生态网络[9 − 10]等领域得到广泛重视。例如：控制疾病传染网络的核心传染源可有效防止病毒大规模扩散[11 − 12]；控制社交舆情网络中关键广播源节点能够有效阻止谣言传播扩散[13 − 14]；对国家电网关键线路采取保护预警措施，可避免电网级联故障蔓延发生；智能控制交通网络中交叉口群交通流及超饱和流，可有效解决阻塞流放大效应[15]。如何准确分析复杂网络中节点重要性，辨识网络关键节点，具有重要的理论意义和现实价值。
复杂网络节点重要性KS辨识分析是对网络节点粗颗粒层级划分以表征网络框架结构特征，可简约对网络整体分层辨识与网络局部分层辨识。同时多种经典节点重要性识别算法被提出，如DC算法[16]、CC算法[17]、BC算法[18]、EC向量算法[19]、PageRank算法[20]等。Bae等[21]提出邻域中心性，用邻居节点Ks值来估计节点在网络中的扩散影响；Zhao等[22]提出多属性节点辨识算法，将网络跨层数与邻居节点两部分以熵加权赋值形式，为节点重要性提供判断依据；Namtirtha等[23]提出加权壳度邻域算法，用可调参数对K壳值和度值作动态调整，进行网络关键节点辨识；卢鹏丽等[24]基于精准K核与信息熵思想提出混合中心性（MC）；王凯莉等[25]用向量表示网络中节点自身Ks值与其多阶邻居Ks值,从而比较网络中节点重要性大小；罗仕龙等[26]认为网络稠密结构会影响节点辨识准确性，提出权重分布指数。为细化复杂网络层级划分，提升网络节点辨识精度，部分研究应用信息熵：Wang等[27]整合K壳和节点信息熵，提出IKS算法，分析不同壳层节点传播能力；胡钢等[28]定义节点邻接信息熵并给出节点重要性识别算法对不同层次节点进行重要性排序；汪亭亭等[29]提出网络跨层因子改进K壳分解算法，计算节点信息熵进行二次辨识，以提升同壳层节点的区分度；王小刚等[30]根据不同节点特征选取不同阶数度量节点，得出多阶邻居在网络中的分布特征信息；洪成等[31]引入参数ω，融合节点相邻时间快照的层间邻域拓扑信息，提出层间邻域信息熵的时序网络节点重要性评估方法。为挖掘复杂网络层间结构与跨层节点之间交互信息：JIANG等[32]基于重力模型，以节点结构洞特性和K壳中心性用概率激励的有效距离代替最短距离，从局部拓扑结构和全局位置两方面识别网络中重要节点方法；王雨等[33]定义多重影响力矩阵计算加权网络中节点重要性；邓凯旋等[34]用节点被删除时的先后次序区分节点重要性；谢丽霞等[35]用综合度评价节点重要性；胡钢等[36]提出时序多层网络熵值结构洞节点重要性辨识模型进行复杂网络关键节点识别；Zhang[37]分析网络节点位置、节点与其邻居局部特征及多层次节点对网络节点交互关联影响，提出K壳和度差指标。
总之，KS算法[38]可对网络中节点重要性进行粗粒化层间范式划分。该方法原理简单，大批次节点被分层同质化，层内节点区分度低适用性差。为保障复杂网络辨识精细化，提升优化复杂网络层级划分，充分利用节点属性跨层信息与层内交互信息，提高节点辨识精度，本文提出一种网络跨层邻度熵（network cross-layer adjacency entropy, NCAE）算法。首先，给出复杂网络跨层数与网络跨层中心性定义，采用网络跨层数对K核分解进行细化，增加相同Ks值的节点区分程度；其次，综合节点的邻居属性和位置属性信息定义复杂网络跨层邻度熵，精细化节点层级辨识，提升节点跨层及层内交互关联影响力；最后，将NCAE算法与DC算法、KS算法、Cnc算法、Cnc+算法和Eksd算法应用于5种不同网络结构与属性特征的真实网络进行对比实验，结果表明，NCAE算法在单调性和精准性等方面表现优于其他对比算法。
1. 网络跨层信息熵系统建模
设存在无向无权网络G=(V，E，A)，其中：V={$ {{v}}_{1} $，$ {{v}}_{2} $，$ \cdot\cdot\cdot $，$ {{v}}_{{n}} $}表示网络节点集合，|V|=n表示网络中节点总数；E={$ {{e}}_{1} $，$ {{e}}_{2} $,$ \cdot\cdot\cdot $，$ {{e}}_{m} $}⊆V×V为网络中边的集合，|E|=m为网络中边的总数；其邻接矩阵为A={$ {a}_{ij} $}，如果节点i和节点j之间存在链接，则$ {a}_{ij} $=1；否则$ {a}_{ij} $=0。此外，$ \varGamma \left(i\right) $通常用于表示节点i的邻居集。复杂网络多属性特征主要用度中心性、介数中心性、邻域中心性等表征。
1.1 网络节点度中心性
度值表示网络节点与其他节点直接通信能力与效用。其数值用相邻节点数量表示，邻居节点数量越多，节点越重要。度中心性一般表示为
$$ D_i=\frac{\sum_j^N a_{i j}}{N-1} $$ (1) 式中：N为网络中节点总数；N$ - $1为归一化因子。
1.2 网络节点邻域中心性
邻域中心性[39]通过将邻居节点Ks值叠加确定节点在网络中扩散影响，网络邻域核心度值越高表示位于网络核心邻居节点越多，网络节点i的邻域核心度Cnc为
$$ \operatorname{Cnc}(i)={\sum}_{j \in \varGamma_i} {\mathrm{K s}}(j) $$ (2) 式中：$ {\varGamma }_{i} $是节点i一阶邻居节点集合；$ \mathrm{Ks}\left(j\right) $是二阶邻居节点j的$ \mathrm{K}\mathrm{s} $值。递归归纳，节点i的邻域中心性$ \mathrm{Cnc}+ $定义为
$$ {\mathrm{C n c}}+(i)=\sum_{j \in {\varGamma}_i} \operatorname{Cn} {\mathrm{c}}(j) $$ (3) 式中$ \mathrm{C}\mathrm{n}\mathrm{c}\left({j}\right) $为节点i的邻居节点j的邻域核心度。
1.3 网络节点信息熵
信息熵[40]可表示复杂网络多属性特征不确定性程度，熵越大，网络属性特征信息的不确定性越大，辨识成本就越高。复杂网络中节点信息熵统计表征网络全局结构，熵越大，节点影响力越大。假设节点i的度数是$ {D}_{i} $，节点的重要性可表示为$I_i=D_i / \sum_{j=1}^N D_j$，其中N为网络中节点数，节点信息熵表示为
$$ e_i=-{\sum}_{j \in r_i} I_j \ln _j $$ (4) 实验统计发现节点信息熵越大则该节点邻居节点数越多，节点的信息传播范围就越广。节点信息熵可以在一定程度上反映节点重要性。
1.4 网络跨层邻度熵
KS算法可为节点重要性进行一种粗粒度划分。Ks值相同的节点被范式化认为具有相同重要性和同等传播能力，导致大量节点被划为同一壳层，忽略跨层与层内节点交互作用与其本身在网络中所处位置信息。为解决KS算法区分程度低等问题，这里提出网络跨层算法思想，利用KS算法分解程序中节点被删除先后顺序细化区分相同壳层节点的重要性程度，如图1所示。
第1步，删除网络中原始度值为1的节点，删除节点为9、15、18、19、20、21、22、25、26，其网络跨层数为1；然后继续删除网络中新出现度值为1的节点，被删除节点为17、24，其网络跨层数为2；迭代上述操作，第3次删除节点为23，其网络跨层数为3。此时网络剩余节点中最小度值至少为2，将上述被删除节点的Ks值赋值为1。
第2步，寻找网络剩余节点中度值为2的节点进行网络跨层删除，第4次被删除节点为8、11、12、13、16，其网络跨层数为4；重复上述操作，网络跨层数为5的节点为14，网络跨层数为6的节点为7、10，网络跨层数为7的节点为6。此时网络中不存在度值为2的节点，网络中剩余节点度值为4，将第2步中所有被删除节点的Ks值赋值为2。
最后，对网络中现存最小度值（示例网络为4）节点进行删除操作，第8次删除节点为1、2、3、4、5，其Ks值设为3。至此网络中全部节点均被删除并已分配相应Ks值与网络跨层数。整个K-shell分解过程记录如表1所示。
表 1 K核分解中的网络跨层数和Ks值Table 1. Number of iterations and Ks value in K-shell decompositionKs值 网络跨层数 删除节点 1 1 9、15、18、19、20、21、22、25、26 1 2 17、24 1 3 23 2 4 8、11、12、13、16 2 5 14 2 6 7、10 2 7 6 3 8 1、2、3、4、5 为融合跨层跨级节点信息，提升节点重要性辨识精度，现给出以下3个定义。
定义1 网络跨层中心性。
从上分析讨论可知，层内相同Ks值的节点之间的差异明显，更能反映网络中节点位置重要性。考虑递归删除顺序节点位置信息的网络跨层中心性可定义为
$$ \mathrm{Kc}(i)=\frac{n_i}{n_{\max}} $$ (5) 式中：$ {n}_{i} $为节点i的网络跨层数；$ {n}_{{\mathrm{max}}} $为归一化因子。
定义2 网络跨层中心度。
该定义将节点删除操作过程的网络跨层数与节点的度融合，表征拥有多邻居节点且处于网络核心的节点应具有更大重要性。网络跨层中心度具体定义为
$$ \mathrm{Dn}(i)=\frac{1}{2}\left(\frac{D_i}{N-1}+\frac{n_i}{n_{\max}}\right) $$ (6) 以图1示例网络中节点23为例，其度值为3，删除时的网络跨层数为3，因此Dn(23)的值为
0.5625 。定义3 网络跨层邻度熵。
网络跨层实现原有层级之间跨层结构细化，将更多的层间与层内节点细分量化，可进一步区分相同位置节点的重要性差异，结合节点邻居信息计算节点的邻域相关度来确定节点在网络中的扩散影响，能更深入集结网络局部特征信息和全局结构信息。基于此，本文提出网络跨层邻度熵来辨识节点在网络中的影响力。网络跨层邻域度定义为
$$ {\mathrm{C d n}}(i)={\sum}_{j \in \varGamma_i} \operatorname{Dn}(j) $$ (7) 式中$ {\varGamma }_{i} $为节点i的邻居节点集合。信息熵从概率与统计角度出发，表征网络节点样本的无序化程度。本文将信息熵融入算法，进行最后结果的总体校准。于是，网络跨层邻度熵的公式为
$${\mathrm{ I N E}}+(i)=e_i {\sum}_{j \in \varGamma_i} {\mathrm{C d n}}(j) $$ (8) 不同网络多属性特征在示例网络中得出的排名结果如表2所示。由表2可知：DC算法（度中心性）与KS算法，在节点重要性排序中都存在大量相同结果；NCAE算法（网络跨层邻度熵）得出的节点排序更细化。这是由于网络跨层邻度熵中所涉及的节点度值、网络跨层数及邻域中心性等包含节点的邻居数量、网络位置、拓扑结构等多重属性特征；又引入信息熵进行最后结果修正，这样不仅可消除网络单一多属性特征评估节点产生的评价片面性，还可进一步精细化区分相似节点的重要性程度，得到更加准确的节点重要性排序结果。与Eksd算法相比，在本文算法识别出的重要节点在网络中数量分布更广、所处位置更多元化，表明本文算法具有更优越的节点辨识性能。
表 2 不同多属性特征指标在示例网络中得出的排名结果Table 2. The ranking results of different metrics in the instance network序号 KS DC Cnc Cnc+ Eksd NCAE 1 1-5 17 1,2,5 2 2 2 2 6-8,10-14,16 1,2,4,5,10 4 1,5 1，5 1，5 3 9,15,17-26 3,6 3 4 4 4 4 7,8,13,14,16,23 10 3 3 3 5 11,12,24 6 6 6 6 6 9,15,18-22,25,26 16,17 16 10 10 7 7,14 10 16 16 8 8 7 7 7 9 13 14 14 14 10 23 13 13 13 11 11,12 23 23 17 12 9,15,24 8,12 8 23 13 18-22,25,26 11 12 8 14 17 11 12 15 18-22 17 11 16 6 9 24 17 9,15,26 15,18-22,24 18-22 18 25 26 15 19 25 9 20 26 21 25 2. 实验分析
2.1 数据集
为测试本文NCAE算法辨识网络关键节点的能力，选取海豚社交网络（Dolphin）[40]、美国大学生足球俱乐部网（Football）[41]、科学家合作网络(Netscience)[42]、大学生电子邮件网络（Email）[43]与仓鼠网络（Hamster)[44]5种不同网络数据集进行仿真实验，具体信息如表3所示。其中：|V|代表网络节点数量；|E|代表网络边数；Ave degree和Max degree分别表示网络的节点平均度值和网络中节点最大度值；$ {\beta }_{{\mathrm{th}}} $和$ \beta $表示网络的传播阈值和感染率。
表 3 真实网络数据集的属性Table 3. Data details of the real networks网络名称 |V| |E| Ave degree Max degree $ {\beta }_{{\mathrm{th}}} $ $ \mathrm{\beta } $ Dolphins 62 159 5.129 12 0.147 0.15 Football 115 613 6.042 12 0.093 0.12 Netscience 379 914 4.820 34 0.125 0.15 Email 1133 5451 9.622 71 0.054 0.07 Hamster 2426 16631 13.711 71 0.054 0.06 2.2 SIR模型
SIR模型[45]可描述信息传播网络。本文利用SIR传播模型对节点在网络中真实影响力进行计算排序。SIR模型中每个节点都可分为以下３种状态：易感状态（S）、感染状态（I）和恢复状态（R）。一个节点$ {v}_{i} $被感染后，其余节点变为易感状态。在每个时间点内，感染节点（I）尝试影响它们的易感邻居节点（S）并以一定的传染概率将它们变成感染状态（I），再以特定的恢复概率转变成恢复状态（R）。
该过程一直持续运行，直到网络中没有处于感染状态（I）的节点，最终处于恢复状态（R）节点数量则被视为SIR过程结束时节点$ {v}_{i} $的传播能力。SIR过程最终获得的所有节点的排名列表$ {Y}_{i}\left(i= \mathrm{1,2},3,\cdots,\left|V\right|\right) $，节点的传播能力通过重复SIR传播过程得出的数据估计。在SIR模拟中，传播概率$ \mathrm{\beta } $的最小值为$ {\beta }_{{\mathrm{th}}} $，其中，$ \beta_{{\mathrm{t h}}}=\langle k\rangle /\langle k^2\rangle$，$ \langle{k}\rangle $和$ \langle{{k}^{2}}\rangle $分别表示网络邻居和二阶邻居的平均度数。本文实验在对网络运行
1000 次SIR模拟，将最终的恢复节点的平均数量视为节点最终的传播能力。2.3 评价方法
2.3.1 单调系数M
引用排序向量R的单调性M[46]来量化不同排序方法的分辨率，具体公式为
$$ M({\boldsymbol{R}})=\left[1-\frac{\sum_{r \in R} n_r\left(n_r-1\right)}{n(n-1)}\right] $$ (9) 式中：n是排名向量R的大小；$ {n}_{r} $指具有相同排名r的联系数。这个度量值是量化排名列表里的关系的比例。单调性M(R)为1时，向量R是完全单调的；单调性M(R)的值为0，则R中的所有节点都有相同的秩。M(R)取值在[0,1]区间内，复杂网络中M(R)值表述算法对网络节点的区分度， M(R)值越接近1，表明算法区分的节点层级越高，则算法具有优越的区分性能。
2.3.2 肯德尔相关系数
为深入考察本文算法准确性，使用Kendall Tau系数(τ)[47]来量化比较不同算法的相关性，τ定义为
$$ \tau({\boldsymbol{R}})=\frac{2\left(N_c-N_d\right)}{N(N-1)} $$ (10) 式中Nc和Nd代表由不同算法实际计算与SIR模型仿真模拟得出的节点重要性排序表之间的相关性一致和不一致的数量。设具有N个节点的2个相关序列X=($ {{x}}_{1} $,$ {{x}}_{2} $,···,$ {{x}}_{{n}} $)和Y=($ {{y}}_{1} $,$ {y}_{2} $,···,$ {{y}}_{{n}} $)，任何一对二元组x=($ {{x}}_{{i}} $,$ {{y}}_{{i}} $)和y=($ {{x}}_{{j}} $,$ {{y}}_{{j}} $)：若$ {{x}}_{{i}} > {{x}}_{{j}} $且$ {{y}}_{{i}} > {{y}}_{{j}} $或$ {{x}}_{{i}} < {{x}}_{{j}} $且$ {{y}}_{{i}} < {{y}}_{{j}} $时，则这2个元素一致；当$ {{x}}_{{i}} > {{x}}_{{j}} $且$ {{y}}_{{i}} < {{y}}_{{j}} $或$ {{x}}_{{i}} < {{x}}_{{j}} $且$ {{y}}_{{i}} > {{y}}_{{j}} $时，它们不一致；$ {{x}}_{{i}}={{x}}_{{j}} $或$ {{y}}_{{i}}={{y}}_{{j}} $时，不计入计算范围。肯德尔系数值的大小必须在[$ - $1,1]的范围内，且越接近于1，表明算法排序结果越准确。
2.4 实验结果分析
2.4.1 单调性
表4数据反映各个算法评估指标性能在5种不同拓扑结构的网络下网络单调性Ｍ。可以看出，KS算法得出的排序结果分辨率最低。其原因是：KS算法给网络大量节点范式化分配相同Ks值；DC算法表现略优于KS算法，仅反映网络局部指标；NCAE算法在所有网络中都具有最高的M值，在大学生邮件网络和仓鼠网络中甚至达到
0.9999 ，表明本文算法具备优秀的节点区分能力。表 4 不同算法在5种真实网络中的单调性ＭTable 4. M-monotonicity of different algorithms in 5 real networks网络 ${M} $ $ \mathrm{K}\mathrm{S} $ $ \mathrm{D}\mathrm{C} $ $ \mathrm{C}\mathrm{n}\mathrm{c} $ $ \mathrm{C}\mathrm{n}\mathrm{c}+ $ $ \mathrm{E}\mathrm{k}\mathrm{s}\mathrm{d} $ $ \mathrm{N}\mathrm{C}\mathrm{A}\mathrm{E} $ Dolphins 0.3769 0.8312 0.9991 0.9873 0.9899 0.9958 Football 0.0003 0.3637 0.9855 0.6778 0.8563 0.8958 Netscience 0.6428 0.7642 0.9991 0.9593 0.9913 0.9983 Email 0.8088 0.8874 0.9855 0.9991 0.9619 0.9999 Hamster 0.8741 0.8980 0.9991 0.9855 0.9899 0.9999 2.4.2 准确性
表5汇总5种不同情况的网络在特定感染率β下各个算法的肯德尔相关系数。表5结果表明：KS算法由于自身局限性，其在所有网络中性能表现均不理想；NCAE算法除了在Hamster网络中表现略逊于Cnc算法，其余4种网络中均表现最佳。综上，NCAE算法在大多数网络中比其他对比算法具有更优秀的性能表现。
表 5 不同算法在5种真实网络中的肯德尔相关系数τTable 5. Kendall correlation coefficient τ of different algorithms in 5 real networks网络 $ \mathrm{\tau } $ $ \mathrm{K}\mathrm{S} $ $ \mathrm{D}\mathrm{C} $ $ \mathrm{C}\mathrm{n}\mathrm{c} $ $ \mathrm{C}\mathrm{n}\mathrm{c}+ $ $ \mathrm{E}\mathrm{k}\mathrm{s}\mathrm{d} $ $ \mathrm{N}\mathrm{C}\mathrm{A}\mathrm{E} $ Dolphins 0.7363 0.7532 0.7704 07992 0.7483 0.8101 Football 0.1021 0.5066 0.5066 0.6144 0.5473 0.6559 Netscience 0.5886 0.6658 0.7200 0.7850 0.7517 0.8049 Email 0.8161 0.8184 0.8195 0.8198 0.7615 0.8466 Hamster 0.7290 0.7474 0.7823 0.7505 0.7242 0.7588 为深入验证NCAE算法对网络中关键节点的辨识能力，消除特殊网络传染率对实验结果的偶然性，在Football网络、Email网络、Hamster网络和Netscience网络阈值附近均匀地选取5种感染率数值进行实验并对比数据结果。如图2所示，在美国大学生足球俱乐部网络、大学生邮件网和科学家合作网络中，不论感染率β如何变化，NCAE算法性能总是明显优于其他节点评估指标。仓鼠网络中，NCAE算法低于Cnc算法，这是由于仓鼠网络中节点位置相对分散，最大Ks值为24，高于同级别大部分网络，网络中层级隶属关系较为清晰，Cnc算法偏重考虑节点直接邻域所有节点的叠加影响力，因此表现好。NCAE算法将节点叠加影响力范围扩大至二步邻域，导致表现效果略有不足，但采用信息熵对结果进行平抑校正，因此综合表现仍能稳居第二。实验数据表明，NCAE算法能更精准有效地辨识复杂网络中关键节点。
![]()
图 2 不同感染率β下各算法的肯德尔相关系数Figure 2. Kendall correlation coefficients of each algorithm under different infection rate β2.4.3 时间性能
为评价NCAE算法的时间性能，本文将不同算法在不同网络中的运行时间进行比较，实验数据在不同网络上进行100次重复实验并计算其平均运行时间，结果如图3所示。DC算法仅计算邻居节点的数量，运行时间短，但识别的准确性和区分度较低；KS算法原理简单，但不能区分同层节点的重要性。除KS算法与DC算法，NCAE方法在不同网络上的运行时间最短，具有较好的时间性能。
3. 结论与展望
识别网络关键节点能够提升网络效率，促进复杂网络与复杂系统相关领域发展，如何准确辨识网络中位置相近节点，一直是复杂网络节点辨识研究中的热点问题。本文首先基于K核分解思想提出网络跨层中心性，并将其与邻域中心性、度中心性以及信息熵三者结合提出网络跨层邻度熵算法，最后在5种不同的常见网络中，通过与几种经典算法进行单调性、准确性及时间性能进行一系列对比实验，结果表明，NCAE算法具备更优秀的关键节点识别能力和时间性能。目前研究针对静态复杂网络，未来研究中，可将此算法推广应用于动态多层复杂网络。
-
![]()
图 2 不同感染率β下各算法的肯德尔相关系数
Figure 2. Kendall correlation coefficients of each algorithm under different infection rate β
表 1 K核分解中的网络跨层数和Ks值
Table 1 Number of iterations and Ks value in K-shell decomposition
Ks值 网络跨层数 删除节点 1 1 9、15、18、19、20、21、22、25、26 1 2 17、24 1 3 23 2 4 8、11、12、13、16 2 5 14 2 6 7、10 2 7 6 3 8 1、2、3、4、5 
下载: 导出CSV
表 2 不同多属性特征指标在示例网络中得出的排名结果
Table 2 The ranking results of different metrics in the instance network
序号 KS DC Cnc Cnc+ Eksd NCAE 1 1-5 17 1,2,5 2 2 2 2 6-8,10-14,16 1,2,4,5,10 4 1,5 1，5 1，5 3 9,15,17-26 3,6 3 4 4 4 4 7,8,13,14,16,23 10 3 3 3 5 11,12,24 6 6 6 6 6 9,15,18-22,25,26 16,17 16 10 10 7 7,14 10 16 16 8 8 7 7 7 9 13 14 14 14 10 23 13 13 13 11 11,12 23 23 17 12 9,15,24 8,12 8 23 13 18-22,25,26 11 12 8 14 17 11 12 15 18-22 17 11 16 6 9 24 17 9,15,26 15,18-22,24 18-22 18 25 26 15 19 25 9 20 26 21 25
下载: 导出CSV
表 3 真实网络数据集的属性
Table 3 Data details of the real networks
网络名称 |V| |E| Ave degree Max degree $ {\beta }_{{\mathrm{th}}} $ $ \mathrm{\beta } $ Dolphins 62 159 5.129 12 0.147 0.15 Football 115 613 6.042 12 0.093 0.12 Netscience 379 914 4.820 34 0.125 0.15 Email 1133 5451 9.622 71 0.054 0.07 Hamster 2426 16631 13.711 71 0.054 0.06
下载: 导出CSV
表 4 不同算法在5种真实网络中的单调性Ｍ
Table 4 M-monotonicity of different algorithms in 5 real networks
网络 ${M} $ $ \mathrm{K}\mathrm{S} $ $ \mathrm{D}\mathrm{C} $ $ \mathrm{C}\mathrm{n}\mathrm{c} $ $ \mathrm{C}\mathrm{n}\mathrm{c}+ $ $ \mathrm{E}\mathrm{k}\mathrm{s}\mathrm{d} $ $ \mathrm{N}\mathrm{C}\mathrm{A}\mathrm{E} $ Dolphins 0.3769 0.8312 0.9991 0.9873 0.9899 0.9958 Football 0.0003 0.3637 0.9855 0.6778 0.8563 0.8958 Netscience 0.6428 0.7642 0.9991 0.9593 0.9913 0.9983 Email 0.8088 0.8874 0.9855 0.9991 0.9619 0.9999 Hamster 0.8741 0.8980 0.9991 0.9855 0.9899 0.9999
下载: 导出CSV
表 5 不同算法在5种真实网络中的肯德尔相关系数τ
Table 5 Kendall correlation coefficient τ of different algorithms in 5 real networks
网络 $ \mathrm{\tau } $ $ \mathrm{K}\mathrm{S} $ $ \mathrm{D}\mathrm{C} $ $ \mathrm{C}\mathrm{n}\mathrm{c} $ $ \mathrm{C}\mathrm{n}\mathrm{c}+ $ $ \mathrm{E}\mathrm{k}\mathrm{s}\mathrm{d} $ $ \mathrm{N}\mathrm{C}\mathrm{A}\mathrm{E} $ Dolphins 0.7363 0.7532 0.7704 07992 0.7483 0.8101 Football 0.1021 0.5066 0.5066 0.6144 0.5473 0.6559 Netscience 0.5886 0.6658 0.7200 0.7850 0.7517 0.8049 Email 0.8161 0.8184 0.8195 0.8198 0.7615 0.8466 Hamster 0.7290 0.7474 0.7823 0.7505 0.7242 0.7588
下载: 导出CSV
-
[1] LI J W, WEN X X, WU M G, et al. Identification of key nodes and vital edges in aviation network based on minimum connected dominating set[J]. Physica A: Statistical Mechanics and Its Applications, 2020, 541: 123340. doi: 10.1016/j.physa.2019.123340
[2] HE H, LIU W G, ZHAO Z H, et al. Vulnerability of regional aviation networks based on DBSCAN and complex networks[J]. Computer Systems Science and Engineering, 2022, 43(2): 643 − 655. doi: 10.32604/csse.2022.027211
[3] SU D, ZHANG Y, WANG L W, et al. Small target detection method based on feature fusion for deep learning in state grid environment evaluation[J]. International Journal of Communication Networks and Distributed Systems, 2022, 28(5): 600. doi: 10.1504/IJCNDS.2022.125378
[4] WANG Y H , XU H , WANG X Y , et al. Optimization of the operation model of intelligent logistics warehousing and distribution of state grid corporation[J]. International Journal of Frontiers in Engineering Technology, 2022, 4(1): 7 − 12.
[5] DONG S J, GAO X Y, MOSTAFAVI A, et al. Characterizing resilience of flood-disrupted dynamic transportation network through the lens of link reliability and stability[J]. Reliability Engineering & System Safety, 2023, 232: 109071.
[6] GORJI M A, AKBARZADEH M, SHETAB-BOUSHEHRI S N. Evaluation and improvement of the urban transportation networks resilience in short-term non-recurring traffic congestion: a novel graph connectivity-based criteria[J]. Transportation Engineering, 2022, 10: 100152. doi: 10.1016/j.treng.2022.100152
[7] HOSSEINI S, ZANDVAKILI A. Information dissemination modeling based on rumor propagation in online social networks with fuzzy logic[J]. Social Network Analysis and Mining, 2022, 12(1): 34. doi: 10.1007/s13278-022-00859-y
[8] INAFUKU K, FUSHIMI T, SATOH T. Predicting stimulation index of information transmissions by local structural features in social networks[J]. Social Network Analysis and Mining, 2022, 12(1): 40. doi: 10.1007/s13278-022-00865-0
[9] GAO C, PAN H Y, WANG M C, et al. Identifying priority areas for ecological conservation and restoration based on circuit theory and dynamic weighted complex network: a case study of the Sichuan Basin[J]. Ecological Indicators, 2023, 155: 111064. doi: 10.1016/j.ecolind.2023.111064
[10] STRYDOM T, DALLA RIVA G V, POISOT T. SVD entropy reveals the high complexity of ecological networks[J]. Frontiers in Ecology and Evolution, 2021, 9: 623141. doi: 10.3389/fevo.2021.623141
[11] GUO Y T, WANG J L, JI D S. Asymptotic profiles of a diffusive SIS epidemic model with vector-mediated infection and logistic source[J]. Zeitschrift Für Angewandte Mathematik Und Physik, 2022, 73(6): 255.
[12] PALAFOX-CASTILLO G, BERRONES-SANTOS A. Stochastic epidemic model on a simplicial complex[J]. Physica A: Statistical Mechanics and Its Applications, 2022, 606: 128053. doi: 10.1016/j.physa.2022.128053
[13] LIU P. Information dissemination mechanism based on cloud computing cross-media public opinion network environment[J]. International Journal of Information Technologies and Systems Approach, 2021, 14(2): 70 − 83. doi: 10.4018/IJITSA.2021070105
[14] WANG G H, CHI Y X, LIU Y J, et al. Studies on a multidimensional public opinion network model and its topic detection algorithm[J]. Information Processing & Management, 2019, 56(3): 584 − 608.
[15] WANG S L, CHEN C, ZHANG J H, et al. Vulnerability assessment of urban road traffic systems based on traffic flow[J]. International Journal of Critical Infrastructure Protection, 2022, 38: 100536. doi: 10.1016/j.ijcip.2022.100536
[16] FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social Networks, 1978, 1(3): 215 − 239. doi: 10.1016/0378-8733(78)90021-7
[17] SABIDUSSI G. The centrality index of a graph[J]. Psychometrika, 1966, 31(4): 581 − 603. doi: 10.1007/BF02289527
[18] FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35. doi: 10.2307/3033543
[19] BONACICH P. Some unique properties of eigenvector centrality[J]. Social Networks, 2007, 29(4): 555 − 564. doi: 10.1016/j.socnet.2007.04.002
[20] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1/7): 107 − 117. doi: 10.1016/S0169-7552(98)00110-X
[21] 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: 549 − 559. doi: 10.1016/j.physa.2013.10.047
[22] ZHAO N, BAO J J, CHEN N. Ranking influential nodes in complex networks with information entropy method[J]. Complexity, 2020, 2020: 5903798.
[23] NAMTIRTHA A, DUTTA A, DUTTA B. Weighted kshell degree neighborhood: a new method for identifying the influential spreaders from a variety of complex network connectivity structures[J]. Expert Systems with Applications, 2020, 139: 112859. doi: 10.1016/j.eswa.2019.112859
[24] 卢鹏丽, 许星舟. 基于精准k核的复杂网络节点重要性评估方法[J]. 兰州理工大学学报, 2022, 48(4): 90 − 98. doi: 10.3969/j.issn.1673-5196.2022.04.014 LU P L, XU X Z. An evaluation method of critical nodes in complex network based on accurate k-shell[J]. Journal of Lanzhou University of Technology, 2022, 48(4): 90 − 98. doi: 10.3969/j.issn.1673-5196.2022.04.014
[25] 王凯莉, 邬春学, 艾均, 等. 基于多阶邻居壳数的向量中心性度量方法[J]. 物理学报, 2019, 68(19): 235 − 245. doi: 10.7498/aps.68.20190662 WANG K L, WU C X, AI J, et al. Complex network centrality method based on multi-order K-shell vector[J]. Acta Physica Sinica, 2019, 68(19): 235 − 245. doi: 10.7498/aps.68.20190662
[26] 罗仕龙, 龚凯, 唐朝生, 等. 加权网络中基于冗余边过滤的k-核分解排序算法[J]. 物理学报, 2017, 66(18): 344 − 353. doi: 10.7498/aps.66.188902 LUO S L, GONG K, TANG C S, et al. A ranking approach based on k-shell decomposition method by filtering out redundant link in weighted networks[J]. Acta Physica Sinica, 2017, 66(18): 344 − 353. doi: 10.7498/aps.66.188902
[27] WANG M, LI W C, GUO Y N, et al. Identifying influential spreaders in complex networks based on improved k-shell method[J]. Physica A: Statistical Mechanics and Its Applications, 2020, 554: 124229. doi: 10.1016/j.physa.2020.124229
[28] 胡钢, 徐翔, 高浩, 等. 基于邻接信息熵的网络节点重要性识别算法[J]. 系统工程理论与实践, 2020, 40(3): 714 − 725. doi: 10.12011/1000-6788-2018-1805-12 HU G, XU X, GAO H, et al. Node importance recognition algorithm based on adjacency information entropy in networks[J]. Systems Engineering Theory & Practice, 2020, 40(3): 714 − 725. doi: 10.12011/1000-6788-2018-1805-12
[29] 汪亭亭, 梁宗文, 张若曦. 基于信息熵与迭代因子的复杂网络节点重要性评价方法[J]. 物理学报, 2023, 72(4): 337 − 347. WANG T T, LIANG Z W, ZHANG R X. Importance evaluation method of complex network nodes based on information entropyand iteration factor[J]. Acta Physica Sinica, 2023, 72(4): 337 − 347.
[30] 王小刚, 闫光辉, 周宁. 多阶邻接分布熵下的复杂网络节点相似性分析方法[J]. 控制理论与应用, 2021, 38(6): 739 − 747. doi: 10.7641/CTA.2021.00463 WANG X G, YAN G H, ZHOU N. Analysis method of nodes similarity with multi-layer adjacency entropy[J]. Control Theory & Applications, 2021, 38(6): 739 − 747. doi: 10.7641/CTA.2021.00463
[31] 洪成, 蒋沅, 严玉为, 等. 基于层间邻域信息熵的时序网络节点重要性评估方法[J]. 复杂系统与复杂性科学, 2024, 21(1): 20 − 27. HONG C, JIANG Y, YAN Y W, et al. A method of evaluating importance of nodes in temporal networks based on inter-layer neighborhood information entropy[J]. Complex Systems and Complexity Science, 2024, 21(1): 20 − 27.
[32] JIANG Y, YANG S Q, YAN Y W, et al. A novel method for identifying influential nodes in complex networks based on gravity model[J]. Chinese Physics B, 2022, 31(5): 058903. doi: 10.1088/1674-1056/ac4226
[33] 王雨, 郭进利. 基于多重影响力矩阵的有向加权网络节点重要性评估方法[J]. 物理学报, 2017, 66(5): 19 − 30. doi: 10.7498/aps.66.050201 WANG Y, GUO J L. Evaluation method of node importance in directed-weighted complex network based on multiple influence matrix[J]. Acta Physica Sinica, 2017, 66(5): 19 − 30. doi: 10.7498/aps.66.050201
[34] 邓凯旋, 陈鸿昶, 黄瑞阳. 一种基于改进K-shell的节点重要性排序方法[J]. 计算机应用研究, 2017, 34(10): 3017 − 3019. doi: 10.3969/j.issn.1001-3695.2017.10.031 DENG K X, CHEN H C, HUANG R Y. Method of node importance ranking based on improved K-shell[J]. Application Research of Computers, 2017, 34(10): 3017 − 3019. doi: 10.3969/j.issn.1001-3695.2017.10.031
[35] 谢丽霞, 孙红红, 杨宏宇, 等. 基于K-shell的复杂网络关键节点识别方法[J]. 清华大学学报(自然科学版), 2022, 62(5): 849 − 861. XIE L X, SUN H H, YANG H Y, et al. Key node recognition in complex networks based on the K-shell method[J]. Journal of Tsinghua University (Science and Technology), 2022, 62(5): 849 − 861.
[36] 胡钢, 牛琼, 王琴, 等. 时序多层网络熵值结构洞节点重要性建模[J]. 浙江大学学报(工学版), 2023, 57(4): 719 − 725. doi: 10.3785/j.issn.1008-973X.2023.04.009 HU G, NIU Q, WANG Q, et al. Modeling of node importance in entropy-value structured hole of temporal multilayer network[J]. Journal of Zhejiang University (Engineering Science), 2023, 57(4): 719 − 725. doi: 10.3785/j.issn.1008-973X.2023.04.009
[37] ZHANG J P , XU H , YANG J , et al. Mining and ranking important nodes in complex network by K-shell and degree difference[C]//Communication in Computer and Information Science. [S. l. ]: [s. n. ], 2018: 371 − 381.
[38] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6: 888 − 893. doi: 10.1038/nphys1746
[39] NIE T Y, GUO Z, ZHAO K, et al. Using mapping entropy to identify node centrality in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 453: 290 − 297. doi: 10.1016/j.physa.2016.02.009
[40] LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54(4): 396 − 405. doi: 10.1007/s00265-003-0651-y
[41] THOMAS E. Election 2004: how bush won and what you can expect in the future [J]. Library Journal, 2005, 56(97): 207 − 208.
[42] GUIMERÀ R, DANON L, DÍAZ-GUILERA A, et al. Self-similar community structure in a network of human interactions[J]. Physical Review E, 2003, 68(6): 065103. doi: 10.1103/PhysRevE.68.065103
[43] KUNEGIS J. Hamsterster full network dataset-KONECT (2014) [EB/OL]. [2020-09-15]. http://konect uni-koblenz.de/networks/petster-hamster.
[44] NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2006, 74(3 Pt 2): 036104.
[45] SHARKEY K J. Deterministic epidemic models on contact networks: correlations and unbiological terms[J]. Theoretical Population Biology, 2011, 79(4): 115 − 129. doi: 10.1016/j.tpb.2011.01.004
[46] WANG X Y, HE G X. Cryptanalysis on an image block encryption algorithm based on spatiotemporal chaos[J]. Chinese Physics B, 2012, 21(6): 060502. doi: 10.1088/1674-1056/21/6/060502
[47] 苏晓萍, 宋玉蓉. 利用邻域“结构洞” 寻找社会网络中最具影响力节点[J]. 物理学报, 2015, 64(2): 5 − 15. SU X P, SONG Y R. Leveraging neighborhood “structural holes” to identifying key spreaders in social networks[J]. Acta Physica Sinica, 2015, 64(2): 5 − 15.
计量
- 文章访问数: 44
- HTML全文浏览量: 2
- PDF下载量: 12
下载:
