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

arXiv comment10 pages, 5 figures, 3 tables

References in corpus (24)

• Emergence of scaling in random networks
• Epidemic processes in complex networks
• Identification of influential spreaders in complex networks
• The Dynamics of Viral Marketing
• Self-similar community structure in organisations
• Subgraph Centrality in Complex Networks
• Influence maximization in complex networks through optimal percolation
• Vital nodes identification in complex networks
• Leaders in Social Networks, the Delicious Case
• Detecting and Tracking the Spread of Astroturf Memes in Microblog Streams
• Efficient Monte Carlo algorithm and high-precision results for percolation
• Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design
• Localization and centrality in networks
• Network dismantling
• A measure of individual role in collective dynamics
• Fast and simple decycling and dismantling of networks
• StaticGreedy: solving the scalability-accuracy dilemma in influence maximization
• Immunization and targeted destruction of networks using explosive percolation
• Predicting percolation thresholds in networks
• Local structure can identify and quantify influential global spreaders in large scale social networks
• Leveraging percolation theory to single out influential spreaders in networks
• Fundamental difference between superblockers and superspreaders in networks
• Analytical study of quality-biased competition dynamics for memes in social media
• Influence maximization in noisy networks

Cited by in corpus (12)

• Hyper-cores promote localization and efficient seeding in higher-order processes
• Top influencers can be identified universally by combining classical centralities
• Relevance of temporal cores for epidemic spread in temporal networks
• Identifying vital nodes by Achlioptas process
• Influence maximization on temporal networks
• Guiding large-scale management of invasive species using network metrics
• Optimal percolation in correlated multilayer networks with overlap
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Effective submodularity of influence maximization on temporal networks
• Who is the best coach of all time? A network-based assessment of the career performance of professional sports coaches
• Influence Maximization: Divide and Conquer
• Maximizing spreading in complex networks with risk in node activation