Consensus Problems on Small world Graphs: A Structural Study

Pedram Hovareshti, Electrical Engineering, University of Maryland College Park

Consensus problems arise in many instances of collaborative control of multi-agent complex systems, where it is important for the agents to act in coordination with the other agents. To reach coordination, agents need to share information. In large groups of agents the information sharing should be local in some sense, due to energy limitation, reliability, and other constraints. A consensus protocol is an iterative method that provides the group with a common coordination variable. However, local information exchange limits the speed of convergence of such protocols. therefore in order to achieve high convergence speed, we should be able to design appropriate network topologies. A reasonable conjecture is that the small world graphs should result in good convergence speed for consensus problems because their low average pairwise path length should speed up the diffusion of information in the system. We address this conjecture by simulations and also by studying the spectral properties of a class of matrices corresponding to consensus problems on small world graphs.