基于Tsallis 熵的复杂网络节点重要性评估方法*

杨松青 蒋沅† 童天驰 严玉为 淦各升

1) (南昌航空大学信息工程学院,南昌 330063)

2) (南京理工大学自动化学院,南京 210094)

复杂网络中节点重要性的评估是网络特性研究中的一项重要课题,相关研究具有广泛的应用.目前提出了许多方法来评估网络中节点的重要性,然而大多数方法都存在评估角度片面或者时间复杂度过高的不足.为了突破现有方法的局限性,本文提出了一种基于Tsallis 熵的复杂网络节点重要性评估方法.该方法兼顾节点的局部和全局拓扑信息,综合考察节点的结构洞特征和K 壳中心性,并充分考虑节点及其邻域节点的影响.为了验证该方法的有效性,本文采用单调性指标、SIR 模型和Kendall 相关系数作为评价标准,在8 个来自不同领域的真实网络上与其他方法进行比较.实验结果表明,此方法能更有效和准确地评估网络节点的重要性,可以显著区分不同节点的重要性.此外,该方法的时间复杂度仅为 O(n2),适用于大型复杂网络.

1 引言

随着网络信息技术的发展与进步,对复杂网络的研究已经在许多领域受到关注.关键节点作为复杂网络的核心要素之一,对网络的结构和功能有着重要影响,被广泛的研究与应用[1-3].例如,通过对电力网络中某关键的调度中心和变电所进行维保,能保证整个电力网络正常运转的稳定性与高效性[4];通过对病毒传播网络中超级传播源实施隔离,能够大幅降低病毒的传播速度和减小扩散范围[5];通过对社……