NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
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.
The Structure of Optimal and Near Optimal Target Sets in Consensus Models
Published
Author(s)
Fern Y. Hunt
Abstract
We consider the problem of identifying a subset of nodes in a network that will enable the fastest spread of information in a decentralized environment. In a model of communication based on a random walk on an undirected graph, the optimal set over all sets of the same or smaller cardinality, minimizes the sum of the mean first arrival times to the set by walkers starting at nodes outside the set. We provide sufficient conditions for the existence of a greedoid that contains feasible optimal and near optimal sets. It may therefore be possible to search for optimal or near optimal sets by local moves in a stepwise manner to obtain near optimal sets that are better approximations than the factor (1 − 1/e) degree of optimality guaranteed by the use of the greedy algorithm.
Hunt, F.
(2014),
The Structure of Optimal and Near Optimal Target Sets in Consensus Models, Special Publication (NIST SP), National Institute of Standards and Technology, Gaithersburg, MD, [online], https://doi.org/10.6028/NIST.SP.500-303
(Accessed October 1, 2025)