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

Area of Science:

• Network Science
• Computational Social Science
• Data Mining

Background:

• Influence maximization identifies key nodes to maximize information spread in networks.
• Standard greedy algorithms are computationally infeasible for large networks, necessitating heuristic approaches.
• Existing heuristic methods often rely solely on network topology, with unclear optimality.

Purpose of the Study:

• To systematically evaluate heuristic methods for influence maximization.
• To determine the performance gap between heuristic methods and optimal greedy algorithms.
• To identify effective and scalable methods for finding influential spreaders.

Main Methods:

• A corpus of 100 real-world networks was used for evaluation.
• Greedy optimization served as the performance baseline on smaller networks.
• Various heuristic methods, including centrality measures and hybrid algorithms, were tested.

Main Results:

• Simple network metrics (adaptive degree, closeness centrality) achieved near-optimal performance.
• Hybrid algorithms combining multiple topological metrics yielded a 2-5% improvement.
• These findings were validated on large-scale networks where greedy optimization is not feasible.

Conclusions:

• Simple network metrics offer a practical and effective solution for influence maximization in large networks.
• Hybrid approaches can further enhance the performance of heuristic methods.
• The study provides strong support for using topological metrics in scalable influence maximization strategies.