Average consensus over small world networks: A probabilistic framework
- 1 January 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 01912216,p. 375-380
Abstract
It has been observed that adding a few long range edges to certain graph topologies can significantly increase the rate of convergence for consensus algorithms. A notable example is the class of ring-structured Watts-Strogatz small world graphs. Building on probabilistic methods for analyzing `small-world phenomena¿, developed in our earlier work, we provide here a probabilistic framework for analyzing this effect. We investigate what graph characteristics lead to such a significant improvement and develop bounds to analyze consensus problems on randomly varying graphs.Keywords
This publication has 19 references indexed in Scilit:
- Consensus Problems on Small World Graphs: A Structural Study2010
- Distributed average consensus with stochastic communication failures2007
- Topology for Global Average Consensus2006
- Ultrafast consensus in small-world networks2005
- Coordination Variables and Consensus Building in Multiple Vehicle Systems2004
- Consensus Problems in Networks of Agents With Switching Topology and Time-DelaysIEEE Transactions on Automatic Control, 2004
- Coordination of groups of mobile autonomous agents using nearest neighbor rulesIEEE Transactions on Automatic Control, 2003
- A Matrix Perturbation View of the Small World PhenomenonSIAM Journal on Matrix Analysis and Applications, 2003
- Laplace eigenvalues and bandwidth-type invariants of graphsJournal of Graph Theory, 1993
- Non-negative Matrices and Markov Chains1981