当前位置： SCI文献检索 > Scientific Reports期刊下所有文献 > 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.

Abstract：

: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.

journal_name

Sci Rep

journal_title

Scientific reports

authors

Erkol Ş,Castellano C,Radicchi F

doi

10.1038/s41598-019-51209-6

subject

Has Abstract

pub_date

2019-10-22 00:00:00

pages

15095

issue

issn

2045-2322

pii

10.1038/s41598-019-51209-6

journal_volume

pub_type

杂志文章

在线工具

Systematic comparison between methods for the detection of influential spreaders in complex networks.