Hunt, F.
(2016),
An Algorithm for Identifying Optimal Spreaders in a Random Walk Model of Network Communication, Journal of Research (NIST JRES), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://doi.org/10.6028/jres.121.008 (Accessed April 24, 2026)
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
An Algorithm for Identifying Optimal Spreaders in a Random Walk Model of Network Communication
Published
Author(s)
Abstract
In a model of network communication based on a random walk in an undirected graph, what subset of nodes (subject to constraints on its size), enable the fastest spread of information? The dynamics of spread is described by a process dual to the movement from informed to uninformed nodes. In this setting, an optimal set A minimizes the sum of the expected first hitting time F(A), of random walks that start at nodes outside the set. In this paper, the problem is reformulated so that the search for solutions to the problem is restricted to a class of optimal and near optimal subsets of the graph. We introduce a sub- modular, non-decreasing rank function,that permits some comparison between the solution obtained by the classical greedy algorithm and one obtained by our methods.Citation
Journal of Research (NIST JRES) -
NIST Pub Series
Pub Type
NIST Pubs
Download Paper
Keywords
random walk, connected graph, network, first hitting time
Citation
Issues
If you have any questions about this publication or are having problems accessing it, please contact [email protected].
Created May 10, 2016, Updated November 10, 2018