基于交叉熵的节点重要性排序算法

摘要

如何高效地度量节点的重要性一直是复杂网络研究的热点问题。在节点重要性研究中，目前已有许多算法被提出用于判断关键节点，然而多数算法局限于时间复杂度过高或评估角度单一。考虑到熵可用于定量描述信息量的大小，因此，提出了一种基于交叉熵的节点重要性排序算法，该算法兼顾了中心节点与其近邻节点之间的整体影响力，并将节点的邻域拓扑信息有机地融合，使用交叉熵值来量化节点之间的信息差异性。为验证该算法的性能，首先采用单调关系、极大连通系数、网络效率以及SIR模型作为评价指标，其次在8个不同领域的真实网络上与其他7种算法进行比较实验。实验结果表明，该算法具有有效性和适用性，此外时间复杂度仅为O(n)，适用于大型网络。

关键词

攻击策略 / 交叉熵 / 复杂网络 / 节点重要性