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

Area of Science:

• Network Science
• Graph Theory
• Combinatorial Optimization

Background:

• Information diffusion models often rely on random walks within networks.
• Identifying optimal seeding sets for rapid information spread is a computationally challenging problem.

Purpose of the Study:

• To determine the optimal subset of nodes for maximizing information spread speed in a network communication model.
• To develop an efficient method for finding near-optimal solutions to this NP-hard problem.

Main Methods:

• Modeling information spread as a process dual to random walks on undirected graphs.
• Defining an objective function based on the sum of expected first hitting times for nodes outside a chosen set.
• Introducing a submodular rank function to compare novel solutions with greedy algorithms.

Main Results:

• The proposed method identifies a set of nodes with a guaranteed rank relative to the optimal set.
• The supermodularity and non-increasing properties of the hitting time function are leveraged.
• A trade-off between the size of evaluated sets (m) and solution quality (ν) is demonstrated.

Conclusions:

• The developed approach offers an efficient way to find high-quality solutions for information spread optimization.
• The method provides theoretical guarantees on solution quality compared to optimal and greedy strategies.
• This research contributes to understanding and optimizing information dissemination in complex networks.