Skip to main content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

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.
Citation
Special Publication (NIST SP) - 500-303
Report Number
500-303

Keywords

random walk on graph, network spread, consensus models
Created December 19, 2014, Updated November 10, 2018