Effects of Topology in Networked Systems: Stochastic Methods and Small Worlds

The topology of a networked control system has critical consequences for its performance. We provide first substantial examples on the effects of topology. Then we proceed to develop a rigorous evaluation of topology effects using stochastic methods inspired from statistical physics and Markov chains. This analysis leads us to proofs on faster convergence of distributed algorithms in networked systems for certain topologies and especially small-world topologies, which are given an ‘efficiency’ characterization. Finally, these results lead to the development of self-organization of such systems in hierarchies that provably improve performance and response.