1. 引言

网络中的关键节点在传播现象的研究中扮演着至关重要的角色[1]，无论是在流行病学[2]、疾病传播[3]还是信息传播[4]等方面。这些关键节点的识别和影响力评估对于理解和控制传播过程具有重要意义。在社交网络中，关键节点往往是那些连接人数众多或能够影响大量人群的用户。这些节点在信息传播过程中起到放大器的作用，能够加速信息的扩散速度和范围[5]。在疾病传播或谣言扩散的网络中，识别关键节点有助于快速定位并采取措施，如隔离或辟谣，从而有效控制传播过程[6][7]。在电力网络中，关键节点的稳定性对整个系统的可靠性至关重要。通过识别这些节点，可以优先加强其保护措施，提高整个网络的抗干扰能力[8][9]。

目前，评估网络中节点影响力的方法众多，包括但不限于中心性指标，例如，度中心性衡量一个节点的连接数[10]，而接近中心性则衡量节点到其他所有节点的平均距离[11]；介数中心性衡量了一个节点在网络中所起到“桥梁”作用的大小，作用越强，即它在连接网络中其他节点对之间的路径上扮演着重要的角色[12]；k-壳分解是一种将网络分解为不同层次的方法，其中k-壳指的是在移除度最高的节点后，剩下的网络中度为k的节点集合[13]；特征向量中心性是基于网络中节点影响力的传递性，即一个节点的影响力不仅取决于其直接连接的节点，还取决于其邻居节点的影响力[14]；PageRank中心性是一种基于随机游走者在网络中的停留时间来评估节点重要性的方法，常用于搜索引擎优化[15]等。

除此之外，还有基于传播动力学模型的方法，例如，Qu等[16]则将邻接节点的感染风险考虑在内，并提出了一种基于SIS模型的中心性方法。Jun等[17]通过计算感染节点以一定概率感染其邻居节点的数量，来量化网络中每个节点的传播能力。此外，一些研究者利用熵的概念来描述网络结构的复杂性。例如，Chen等[18]提出结构熵来度量网络的复杂性。张齐[19]提出一种基于非广延统计力学的结构熵来度量网络的复杂性。胡钢等[20]通过一种邻接信息熵来识别复杂网络中的重要节点。吴英晗等[21]提出了一种利用节点传播熵识别超网络中重要节点的方法。尽管这些方法在识别关键节点方面取得了一定成果，但它们往往忽略了节点的局部和全局结构信息的综合考量，且在细微区分不同节点方面存在局限。为了解决这些问题，本研究提出了一种新的方法，该方法结合了传播动力学模型和信息熵，旨在更全面地评估网络中节点的传播能力。通过这种方法，我们不仅考虑了节点的局部传播特性，还整合了其邻居节点的传播能力，从而实现了对网络中关键节点的更准确识别和区分。

2. 相关知识

2.1. 复杂网络定义

在研究复杂网络时，通常采用图论的方法来构建模型。具体来说，一个网络可以通过一个图G来表示，该图由两部分组成：节点集V和边集E。在这个模型中，V包含了网络中的所有节点，记为 $V=\left\{v_1,v_2,v_3,\cdots ,v_{\left|V\right|}\right\}$，而E则包含了网络中所有的连接，记为 $E=\left\{e_1,e_2,e_3,\cdots ,e_{\left|E\right|}\right\}$。为了便于分析，网络的连接关系可以通过一个邻接矩阵 $A=a_{ij}\in V\times V$来表示。在这个矩阵中，如果 $a_{ij}$的值为1，则表示节点 $v_i$与节点 $v_j$之间存在直接的连接；如果 $a_{ij}$的值为0，则表示这两个节点之间没有直接的连接。本研究中，我们假设所有考虑的网络都是无向的，即边是双向的，没有指定的方向。

2.2. 度中心性

度中心性[10]定义了节点的一阶邻居数作为其传播影响的度量，表示为：

$DC\left(i\right)=\frac{k\left(i\right)}{N-1}$(1)

其中k(i)表示节点i的度，N是网络中节点的总数。

2.3. 介数中心性

介数中心性[12]定义了作为两个不相连群体之间桥梁角色的节点作为传播影响节点，表示为：

$BC\left(i\right)={\displaystyle \underset{u\ne i\ne v}{\sum }\frac{g_{uv}^i}{g_{uv}}}$(2)

其中 $g_{uv}$表示节点v和节点u之间的最短路径数， $g_{uv}^i$表示通过节点i的节点v和节点u之间的最短路径数。

2.4. K-Shell

k-核值[13]能够反映节点的位置。具体而言，k-核值根据节点的度递归地移除节点，将节点分割成不同的层次来获得。

2.5. SPC模型

SPC算法[17]是一种基于信息传播和感染动态来识别复杂网络中具有影响力的节点的模型。表示为：

$SPC\left(i\right)={\displaystyle \underset{j\in R_i^3}{\sum }{\alpha }^{d_{ij}}}$(3)

其中， $R_i^3$表示节点i的三阶邻居节点集合， $d_{ij}$表示节点i和节点j之间的最短路径长度， $\alpha$是一个可调参数，代表信息从节点i到节点j的传播概率。

2.6. ESPE算法的提出

在网络科学和复杂系统的研究中，用户影响通常被定义为一个用户促使其他用户采取特定行为的能力。在本文中，我们依据易感者–感染者(SI)模型，将一个节点作为感染源并衡量其感染网络中其他未感染节点的能力，以此作为该节点影响力的量化指标。具体而言，节点的传播能力可以通过计算该节点感染未感染邻居节点的概率来确定。然而，一个节点的影响力并非仅由其自身的属性决定，还受到其邻居节点影响力的影响。因此，一个节点的总体影响力应该是由其自身的影响力和其邻居节点影响力的综合效应所共同决定的。为了准确评估这种复合影响力，本文通过结合信息熵，同时考虑节点自身的传播影响力及其邻居节点的传播影响，提出了一种传播概率熵(Epidemic Spreading Probability Entrop, ESPE)的模型，该模型不仅考虑了节点的直接传播能力，还考虑了其邻居节点的传播潜力。

ESPE模型的实施步骤可以概括如下：

1)节点状态初始化：首先，需要确定网络中每个节点的当前状态，这可以是易感者、感染者或传播者。

2)识别三阶邻居节点集：对于目标节点i，识别其所有直接相连的邻居节点，即三阶邻居节点集合 $R_i^3$。

3)计算单个节点的传播概率：对于目标节点i的每一个三阶邻居节点j，计算节点i传播给节点j的概率 $SP\left(i\right)$。这通常基于节点之间的连接强度和网络的拓扑结构。

$SP\left(i\right)={\displaystyle \underset{j\in R_i^3}{\sum }{\alpha }^{d_{ij}}}$(4)

其中， $\alpha$是传播概率的衰减因子， $d_{ij}$是节点i到其三阶邻居j之间的距离。

4)计算节点的总传播概率：累加节点i的所有一阶邻居节点的SP值，得到 $TSP\left(i\right)$：

$TSP\left(i\right)={\displaystyle \underset{j\in R_i^1}{\sum }SP\left(i\right)}$(5)

5)确定信息传播的概率分布：使用 $SP\left(i\right)$和 $TSP\left(i\right)$来确定信息从节点i传播到其每一个一阶邻居节点j的概率 $p\left(j\right)$：

$p\left(j\right)=\frac{SP\left(j\right)}{TSP\left(i\right)}$(6)

6)计算传播影响概率熵：最后，计算目标节点i的传播影响概率熵 $ESPE\left(i\right)$，这反映了节点i对其邻居节点影响力的不确定性或信息的混乱程度：

$ESPE\left(i\right)=-{\displaystyle \underset{j\in R_i^1}{\sum }p\left(j\right)\times \ln \left[p\left(j\right)\right]}$(7)

3. 实验分析

3.1. 数据集

为了全面地评估ESPE算法的性能，本文使用以下六个真实网络，这些网络相关的统计特征如表1所示。1) LastFM[22]：该网络由亚洲地区的LastFM用户组成，用户之间的连接关系基于相互的追随关系。2) Jazz[23]：此网络展现了爵士音乐家之间的合作关系，节点代表音乐家，边代表他们之间的合作。3) Email[24]：该网络基于西班牙塔拉戈纳的Rovirai Virgili大学(URV)的内部电子邮件通信数据构建，其中节点代表组织成员，包括员工、研究人员等，边代表他们之间的电子邮件往来。4) Faa[25]：是https://networkrepository.com/网站上的一个网络。5) Facebook[26]：这个网络由Facebook用户及其朋友构成，每个节点代表一个用户，节点间的连接表示朋友关系。6) Vote[27]：该网络由维基百科用户之间的投票关系构成，节点代表用户，有向边代表用户之间的投票行为。在本研究中，这些有向边被处理为无向边以简化分析。

3.2. 评价标准

3.2.1. SIR模型

SIR模型[28]是流行病学中用于描述传染病传播的典型模型，它将人群分为三个主要状态：易感者(Susceptible, S)、感染者(Infected, I)和康复者(Recovered, R)。在该模型中，每个感染节点以概率h将其感染状态传播给其易感的直接邻居，同时以概率b恢复并退出感染状态。恢复后的节点不会再被感染。这个过程会持续进行，直到网络中没有新的感染发生，达到一个稳定状态。

为了评估节点的感染能力，我们首先将特定节点设定为初始感染状态，而其他所有节点设为易感状态。通过模拟网络达到稳定状态的过程，我们可以统计出在最终状态下的感染节点数和恢复节点数。节点的感染能力，即其标签，可以通过1000次独立实验的平均结果来确定，以提高评估的准确性并减少随机波动的影响。感染能力的计算公式为：

$IC\left(x\right)=\frac{{\displaystyle {\sum }_{j=1}^{1000}{N}_j^i+N_j^r}}{1000\times N}$(8)

其中， $IC\left(x\right)$表示节点x的感染能力， $N_j^i$和 $N_j^r$表示在第j个实验中感染节点和恢复节点的数量。

此外，为了量化网络中感染传播的难易程度，我们引入了感染传播阈值 ${\beta }_{th}$，该阈值可以通过平均场理论来估算。具体计算公式如下：

${\beta }_{th}=\frac{\langle k\rangle }{\langle k^2\rangle -\langle k\rangle }$(9)

其中，k表示节点的度， $\langle \cdot \rangle$表示计算平均值。

通过这种方法，SIR模型不仅能够模拟传染病的传播过程，还可以用于评估个体节点在网络中的感染能力，以及整个网络对疾病传播的抵抗性。这些信息对于设计有效的疾病控制策略和提高网络的鲁棒性具有重要意义。

Table 1.Statistical attributes of six real-world networks

表1.六个真实网络的统计属性

其中n和m分别是网络中的节点总数和边总数， $\langle k\rangle$是网络的平均度， $k_{\max }$是网络的最大度，c是网络的平均聚类系数， $G_{C_V}\text{\%}$和 $G_{C_E}\%$分别表示网络中最大组件中节点和边占总节点数和总边数的比例，d是网络的密度， ${\beta }_{th}$是网络的传播阈值。若网络的 $G_{C_V}\%\approx 100$且 $G_{C_E}\%\approx 100$，则它是一个连通网络，否则它是一个非连通网络。

3.2.2. 肯德尔相关性系数

在本文中，我们采用了肯德尔相关系数(Kendall’s tau coefficient)[29]来衡量两组排名之间的关联程度。肯德尔相关系数的计算公式如下：

$\tau =\frac{2\left(N_c-N_d\right)}{N_L\left(N_L-1\right)}$(10)

在这个公式中， $N_L$是排名列表中的节点数量， $N_c$和 $N_d$分别是一致对和不一致对的数量。具体来说，对于两个数据对 $\left(x_i,y_i\right)$和 $\left(x_j,y_j\right)$，如果 $x_i>x_j$且 $y_i>y_j$，或 $x_i<x_j$且 $y_i<y_j$，则这一对数据 $\left(x_i,y_i\right)$和 $\left(x_j,y_j\right)$是一致的。如果 $x_i>x_j$且 $y_i<y_j$，或 $x_i<x_j$且 $y_i>y_j$，则这一对数据 $\left(x_i,y_i\right)$和 $\left(x_j,y_j\right)$是不一致的。如果 $x_i=x_j$， $y_i=y_j$，这对既不是一致的也不是不一致的。

肯德尔相关系数的取值范围从−1到1。当 $\tau$的值越接近1，表明两个排名列表的一致性越高。如果 $\tau =1$，则表示两个排名完全一致。当 $\tau =0$，表明排名列表之间没有显著的相关性。而当 $\tau =-1$，则意味着两个排名列表完全相反。

在本文的第3.3.1节中，我们将利用 $\tau$来评估由SIR模型产生的排名与通过ESPE模型以及其他方法得到的排名之间的关联性。通过这种方法，我们可以定量地分析不同排名方法之间的一致性和差异性，为进一步的研究提供依据。

3.2.3. 改进率

该性能指标旨在衡量所提出方法相较于其他现有方法在识别性能上的提升幅度。改进率是基于所提方法的识别准确率与对比方法的识别准确率之间的差异百分比来计算的。具体来说，这个指标反映了所提方法在识别准确率上相对于其他方法的增长或减少的幅度。当这个百分比值为正时，意味着所提方法在性能上优于对比方法；若为负，则意味着性能有所下降。此指标是评估新方法在竞争性方法面前性能优势的重要工具。

$\eta \%=\frac{ESPE\left(\tau \right)-SPC\left(\tau \right)}{SPC\left(\tau \right)}\times 100$(11)

其中， $ESPE\left(i\right)$表示所提出方法的肯德尔相关性系数，而 $SPC\left(i\right)$表示SPC算法的肯德尔相关性系数。通过这个公式，我们可以定量地评估所提出方法在识别任务上相对于SPC算法的改进情况，进而为选择更合适的方法提供决策依据。

3.3. 实验结果

3.3.1. 算法的节点排序能力

从图1的分析结果可以观察到，ESPE算法实现了较高的肯德尔相关系数，这揭示了ESPE算法生成的节点排名与实际SIR传播模型的一致性较高。本研究进一步通过将SPC算法设定为对照组，来评估 ESPE算法在肯德尔相关系数上相较于SPC算法的改进程度。

图2的数据揭示了ESPE算法在六个真实网络中都展现了正向的改进，意味着其性能超越了SPC算法。具体来看，在Vote网络中，ESPE算法的平均改进率达到了5.98%，在Jazz网络中达到了9.80%，在LastFM网络中为4.96%，在Email网络中为5.88%，在Facebook网络中显著达到了18.77%，在Faa网络中则为5.38%。这些结果表明，ESPE算法在识别网络中关键节点的准确性方面具有优势，能够更有效地捕捉节点间的复杂关系，从而为关键节点的识别提供了更加精确的方法。

综上所述，ESPE 算法在多个真实网络结构上的表现均优于SPC算法，尤其在Facebook网络中的改进表现尤为突出。这证明了ESPE算法在网络分析中的潜力和实用性，尤其是在需要高精度识别网络关键节点的应用场景中。

Figure 1.Comparative analysis of node rankings generated by centrality measures such as ESPC and SIR: A Kendall’s tau correlation approach

图1.使用ESPC等中心性方法产生的节点排名与SIR产生的节点排名进行比较得到的肯德尔相关系数

Figure 2.Improvement rate of the ESPC algorithm over the SPC algorithm

图2.ESPC算法相对于SPC算法的改进率

Table 2.Top 10 vidal nodes ıdentified by the ESPE method and other approaches across various networks

表2.使用ESPE方法和不同网络中的其他方法计算出的前10个重要节点

续表

3.3.2. 算法在识别头部节点的传播性能

为了更清楚地验证算法在识别网络中关键节点传播能力方面的性能，本研究通过表2对不同网络中被识别为最重要的前10个节点进行了比较分析。使用ESPE算法与其他基线方法进行对比，结果如下。

对于Facebook网络，ESPE算法的识别结果与其他算法相比略逊一筹。然而在其他5个真实网络中，本文所提出的算法在所有比较的基线方法中与SIR模型匹配的节点数量均是最高的。具体而言，在LastFM网络中，ESPE算法与SIR模型识别出的前10个节点有6个是重合的。在Email网络中，ESPE算法与SIR模型匹配的节点数量为8个。在Jazz网络、Vote网络和Faa网络中，ESPE算法与SIR模型一致的节点数量均为8个。

综合考虑，与其它基线方法相比，ESPE算法在识别网络中最关键的前10个节点方面整体表现更为优秀。这一结果表明ESPE算法在捕捉网络中节点的重要性和传播影响力方面具有较高的准确性和可靠性，尤其是在Email网络、Jazz网络、Vote网络和Faa网络中，ESPE算法展现出了其在识别头部节点方面的显著优势。

3.3.3. ESPE与SPC算法相关性对比

为了评估ESPE算法与SPC算法在区分网络节点传播影响力上的能力，图3展示了两种算法得到的排名分数之间的相关性分析。在此图中，X轴代表ESPE算法计算得到的归一化传播影响力，而Y轴代表SPC算法得出的相应数据。每个数据点的颜色基于SIR模型模拟得到的节点传播影响力而定，这使得我们可以通过观察点的分布和颜色来评估两种算法的识别效率。

Figure 3.Correlation of normalized propagation ımpact scores between ESPC and SPC algorithms across six real-world networks

图3.ESPC算法和SPC算法对6个真实网络的归一化传播影响得分之间的相关性

从图3的观察结果可以得出，在所有六个真实世界的网络数据集上，ESPE与SPC算法的排名分数呈现出正相关性。特别地，在LastFM和Facebook网络中，ESPE算法为具有较高传播影响力的红色节点赋予了更高的评分，而在蓝色节点上，SPC算法则给出了相对较高的评分。这一现象表明ESPE算法在辨别传播影响力节点的准确性和分辨率方面优于SPC算法。

这一发现强调了ESPE算法在识别网络中具有显著传播能力节点方面的优越性，尤其是在区分节点传播影响力的细微差别时。ESPE算法通过更精确地量化节点的传播潜力，为网络分析提供了一种改进的方法，这在复杂网络的结构和行为分析中具有重要的应用价值。

4. 结论

本文提出了一种新颖的评估复杂网络中节点重要性的方法，即传播概率熵(ESPE)。与之前的SPC算法相比，ESPE方法在评估节点传播影响力时，不仅考虑了节点自身的传播潜力，还综合了其邻居节点的传播影响，通过信息熵的概念提供了一种更全面的分析框架。为了验证ESPE方法的有效性，本研究采用了肯德尔相关系数来衡量算法的准确性。模拟实验的结果表明，ESPE算法在识别节点传播能力方面得到的肯德尔相关系数普遍高于其他现有方法。特别是在确定网络中最重要的前10个节点时，ESPE算法与SIR传播模型的一致性更高，六个不同网络中的平均改进率达到了8.46%，这进一步证实了ESPE方法的优越性。

此外，通过对比ESPE算法和SPC算法得到的归一化传播影响得分的相关性分析，ESPE算法展现了更高的准确性和区分度。这一发现表明，ESPE算法在识别网络中具有显著传播影响力的节点方面，能够提供更为精确的评估。综上所述，ESPE算法在复杂网络节点重要性评估领域提供了一种新的有效工具。它不仅提高了关键节点识别的准确性，还增强了对这些节点的区分能力，这对于网络分析和相关领域的研究具有重要的理论和实践意义。

尽管ESPE算法在本研究中表现出了显著的优势，未来的工作仍需在更广泛的网络类型和更复杂的传播场景中进一步验证其性能。此外，算法的计算效率和可扩展性也是未来研究的重要方向。我们期待ESPE算法能够在网络科学、信息传播、疾病控制等领域发挥更大的作用，并为相关领域的研究者提供强有力的分析工具。

参考文献