Skip to main content
U.S. flag

An official website of the United States government

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.

Optimal Spread in Network Consensus Models

Published

Author(s)

Fern Y. Hunt

Abstract

Suppose we seek a set of nodes in a network that will enable the fastest spread of information in a decentralized communication environment. If communication resources are limited there are constraints on the number of nodes that can be selected. In this presentation, communication is modeled as a random walk on an undirected graph to the set. The desired set minimizes F(A), the sum of the mean first arrival times by walkers starting at nodes outside A. The function F is supermodular and non-decreasing and thus it falls into the class of functions that are the subject of intense current research in combinatorial optimization and application areas including the security of sensor networks, machine learning and image analysis. The problem of node selection as originally stated is probably NP hard. We discuss a new approach that leverages properties of the underlying graph to produce exact or approximate solutions of pre-defined quality. The method requires some pre-processing and we provide a rough analysis that quantifies the tradeoff between solution quality and computational effort when F has bounded curvature.
Proceedings Title
Proceedings of the International Workshop on Randomization and Computation
Conference Dates
August 24-26, 2015
Conference Location
Princeton, NJ

Keywords

optimal spread, networks, random walks, greedoid theory

Citation

Hunt, F. (2014), Optimal Spread in Network Consensus Models, Proceedings of the International Workshop on Randomization and Computation, Princeton, NJ, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=915155 (Accessed April 22, 2024)
Created January 26, 2014, Updated September 30, 2020