Efficient collective influence maximization in cascading processes with first-order transitions.

Area of Science:

• Network Science
• Complex Systems Dynamics
• Computational Social Science

Background:

• Collective dynamics in social and biological networks are often driven by influential units via global cascading processes.
• These cascades can lead to abrupt changes in system behavior, known as first-order transitions.
• Efficiently identifying multiple influential spreaders is crucial for controlling these processes but remains a significant challenge for large-scale networks.

Purpose of the Study:

• To develop a scalable algorithm for identifying influential spreaders in large-scale networks within general threshold models of cascading processes.
• To understand the fundamental role of subcritical paths in determining spreader importance for global cascades.

Main Methods:

• Analysis of collective influence in general threshold models.
• Introduction and utilization of the concept of 'subcritical paths' to quantify spreader importance.
• Development of a scalable algorithm based on subcritical path analysis for large networks.

Main Results:

• Spreader importance is determined by the number of subcritical paths attached to them, which dictates their contribution to global cascades.
• The proposed algorithm is scalable for massively large networks.
• Empirical results on synthetic random graphs and real-world networks demonstrate superior collective influence compared to other scalable heuristic methods for the same number of seed nodes.

Conclusions:

• The subcritical path concept provides a novel and effective metric for identifying influential spreaders.
• The developed scalable algorithm offers an efficient solution for the critical problem of spreader identification in large complex networks.
• This approach has significant implications for controlling and optimizing cascade processes in various network applications.