Optimal Spread in Network Consensus Models

Published

January 27, 2014

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

Pub Type

Conferences

Download Paper

Local Download

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 26, 2024)