基于扩展度的复杂网络传播影响力评估算法∗

摘要

Evaluating influential spreaders in networks is of great significance for promoting the dissemination of beneficial information or inhibiting the spreading of harmful information. Currently, there are some central indices that can be used to evaluate spreading influence of nodes. However, most of them ignore the spreading probability and take into consideration only the network topology or the location of source node, so the excellent results can be achieved only when the spreading probability is in a specified range. For example, the degree centrality is appropriate for a minor spreading probability, but to ensure the accuracy, semi-local and closeness centralities are more suitable for a slightly larger one. To solve the sensitivity problem of spreading probability, a novel algorithm is proposed based on the extension of degree. In this algorithm, the coverage area of degree is recursively extended by the overlapping of degree of neighbors, which makes different extension levels correspond to different spreading probabilities. For a certain spreading probability, the proper level index is calculated by finding the most correlate ranking sequences of sampling nodes, which is obtained by matching the results of different spreading levels and SIR simulation. In this paper, the relationship between extension level and spreading probability is explained by the theory of fitting the weight and infected possibility of nodes, and the feasibility of the sampling method is verified by the computational experiments. The experimental results on both real and computer-generated datasets show that the proposed algorithm can effectively evaluate the spreading influences of nodes under different spreading probabilities, and the performance is close or even superior to that evaluated by using other central indices.%对网络中节点的传播影响力进行评估具有十分重要的意义，有助于促进有益或抑制有害信息的传播。目前，多种中心性指标可用于对节点的传播影响力进行评估，然而它们一般只有当传播率处于特定范围时才能取得理想的结果。例如，度值中心性指标在传播率较小时较为合适，而半局部中心性和接近中心性指标则适用于稍大一些的传播率。为了解决各种评估指标对传播率敏感的问题，提出了一种基于扩展度的传播影响力评估算法。算法利用邻居节点度值叠加的方式对节点度的覆盖范围进行了扩展，使不同的扩展层次对应于不同的传播率，并通过抽样测试确定了适合于特定传播率的层次数。真实和模拟数据集上的实验结果表明，通过扩展度算法得到的扩展度指标能在不同传播率下对节点的传播影响力进行有效评估，其准确性能够达到或优于利用其他中心性指标进行评估的结果。