Probing Limits of Information Spread with Sequential Seeding.

Area of Science:

• Network science
• Information diffusion modeling

Background:

• Information spread occurs through diffusion cascades initiated by node activation.
• Current methods often use single-stage seeding, activating nodes at once.
• Optimizing spread coverage is crucial for various applications.

Purpose of the Study:

• To introduce and analyze a novel sequential seeding approach for information spread.
• To formally prove the efficacy of sequential seeding against single-stage methods.
• To compare sequential seeding with existing algorithms, including the greedy approach.

Main Methods:

• Development of a coordinated randomized execution for comparing algorithms.
• Application of sequential seeding where newly activated nodes spread information in stages.
• Formal proof of sequential seeding's coverage advantage over single-stage seeding.
• Experimental evaluation on directed and undirected graphs.

Main Results:

• Sequential seeding provides at least as good, and often provably better, spread coverage than single-stage seeding with the same number of seeds.
• A simple degree-based sequential seeding strategy achieved higher coverage than the computationally intensive greedy approach.
• Experimental results quantify the benefits of sequential seeding.

Conclusions:

• Sequential seeding is a more effective strategy for maximizing information spread compared to traditional single-stage methods.
• The proposed method offers a significant improvement over existing heuristics, including the greedy approach.
• Sequential seeding presents a computationally efficient and highly effective alternative for network-based information dissemination.