An Algorithm for Identifying Optimal Spreaders in a Random Walk Model of Network Communication

Area of Science:

• Network Science
• Information Dissemination
• Combinatorial Optimization

Background:

• Information spread in networks is crucial for communication.
• Identifying optimal node sets for fast spread is computationally challenging (NP-hard).
• Existing methods rely on minimizing expected first hitting times, a supermodular function.

Purpose of the Study:

• To find a computationally feasible method for identifying node subsets that enable fastest information spread.
• To develop a new optimization approach that restricts the search space for solutions.
• To analyze the performance of the new method against classical greedy algorithms.

Main Methods:

• Reformulating the combinatorial optimization problem.
• Introducing a submodular, non-decreasing rank function (ρ).
• Analyzing the properties of the expected first hitting time function (F) and the new rank function.

Main Results:

• The proposed method finds near-optimal subsets with a guaranteed performance bound (at least 1/2 times the optimal rank).
• The bound improves to a factor involving χ > 0 when the solution's rank exceeds the greedy solution's rank.
• The method requires evaluating F for smaller set cardinalities (m) compared to the optimal set size.

Conclusions:

• The new approach provides a practical way to identify effective node sets for information spread.
• A trade-off exists between the size of evaluated sets (m) and the quality of the solution (ν).
• The study offers theoretical guarantees for the performance of the proposed optimization technique.