Systematic comparison between methods for the detection of influential spreaders in complex networks
Systematic comparison between methods for the detection of influential spreaders in complex networks
复制标题
DOI：
10.1038/s41598-019-51209-6
复制
发表时间：
2019-10-22
影响因子：
4.6
通讯作者：
Radicchi, Filippo
中科院分区：
文献类型：
--
作者：
Erkol, Sirag;Castellano, Claudio;Radicchi, Filippo
影响最大化是寻找网络中的节点集合，使网络上发生的传播过程的爆发规模最大化的问题。这个问题的解决方案对于营销和政治活动中的战略决策非常重要。典型的设置包括在非常大的网络中识别初始传播者的小集合。这种设置使得优化问题在计算上对于同时考虑关于网络拓扑和传播动态的信息的标准贪婪优化算法是不可行的，仅将空间留给基于仅依赖于网络的几何形状的剧烈近似的启发式方法。关于这个主题的文献是大量的纯拓扑方法，用于识别网络中有影响力的传播者。然而，目前还不清楚这些方法离最佳状态有多远。在这里，我们进行了系统的测试的性能的众多启发式方法识别有影响力的传播者。我们量化了各种方法在100个真实网络的语料库上的性能;语料库由足够小的网络组成，可以应用贪婪优化，因此该算法的结果可以用作分析其他方法在同一网络语料库上的性能所需的基线。我们发现，相对简单的网络指标，如自适应度或接近中心，能够实现性能非常接近的基线值，从而提供了很好的支持，这些指标在大规模的问题设置。此外，我们表明，进一步提高2-5%的基线性能是可以实现的混合算法，联合收割机结合两个或更多的拓扑度量在一起。这个最终的结果是验证了一个小的收集大型图贪婪优化是不适用的。
Influence maximization is the problem of finding the set of nodes of a network that maximizes the size of the outbreak of a spreading process occurring on the network. Solutions to this problem are important for strategic decisions in marketing and political campaigns. The typical setting consists in the identification of small sets of initial spreaders in very large networks. This setting makes the optimization problem computationally infeasible for standard greedy optimization algorithms that account simultaneously for information about network topology and spreading dynamics, leaving space only to heuristic methods based on the drastic approximation of relying on the geometry of the network alone. The literature on the subject is plenty of purely topological methods for the identification of influential spreaders in networks. However, it is unclear how far these methods are from being optimal. Here, we perform a systematic test of the performance of a multitude of heuristic methods for the identification of influential spreaders. We quantify the performance of the various methods on a corpus of 100 real-world networks; the corpus consists of networks small enough for the application of greedy optimization so that results from this algorithm are used as the baseline needed for the analysis of the performance of the other methods on the same corpus of networks. We find that relatively simple network metrics, such as adaptive degree or closeness centralities, are able to achieve performances very close to the baseline value, thus providing good support for the use of these metrics in large-scale problem settings. Also, we show that a further 2-5% improvement towards the baseline performance is achievable by hybrid algorithms that combine two or more topological metrics together. This final result is validated on a small collection of large graphs where greedy optimization is not applicable.