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

Node Importance Ranking Algorithm Based on Cross Entropy

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

     

    Abstract: How to efficiently measure the importance of nodes has been a hot issue in the research of complex networks. In the research of node importance, many algorithms have been proposed to judge key nodes, but most of them are limited to high time complexity or single evaluation angle. Considering that entropy can be used to quantitatively describe the amount of information, this paper proposes a node importance ranking algorithm based on cross entropy. This algorithm takes into account the overall influence among the central node and its neighbor nodes, organically fuses the neighborhood topology information of nodes, and uses cross entropy to quantify the information differences between nodes. In order to verify the performance of the algorithm, this paper first uses monotone relation, maximum connectivity coefficient, network efficiency and SIR model as evaluation indicators, and then compares with other seven algorithms on eight real networks in different fields. The experimental results show that the algorithm proposed in this paper is effective and applicable, and the time complexity is only O(n) , which is suitable for large networks.

     

/

返回文章
返回