Manufacturing consent
Authors:
- 1 September 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1550-1555
Abstract
A scheme for consensus formation is considered wherein the value of a certain variable associated with the nodes of a network is fixed a priori for a prescribed set of K nodes, and allowed to propagate throughout the network through an averaging process that mimics a gossip algorithm. The objective is to find the best choice of these K nodes that will achieve the fastest convergence to consensus. This objective is captured by the Perron-Frobenius eigenvalue of the resultant sub-stochastic matrix, which then is the quantity one seeks to minimize. We propose an algorithm for this optimization problem, as well as a greedy scheme with some performance guarantees for a variant of the problem that seeks to minimize a simpler objective. Some other related formulations are also considered.Keywords
This publication has 9 references indexed in Scilit:
- Finding community structure in networks using the eigenvectors of matricesPhysical Review E, 2006
- Fastest Mixing Markov Chain on a GraphSIAM Review, 2004
- An O(n) Algorithm for Projecting a Vector on the Intersection of a Hyperplane and a Box in RnJournal of Optimization Theory and Applications, 2003
- Risk-Sensitive Optimal Control for Markov Decision Processes with Monotone CostMathematics of Operations Research, 2002
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- A First Course in Optimization Theory1996
- A successive projection methodMathematical Programming, 1988
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978