Robustness of Complex Networks with Implications For Consensus and Contagion

Complex networks (both natural and engineered) arise as a result of local interactions between various agents. The efficacy of these networks is often predicated on their ability to diffuse information throughout the network. We study two special cases of diffusion: resilient consensus (where agents synchronize on a quantity of interest despite the actions of adversaries) and contagion (where information held by a few individuals cascades through the rest of the network). We characterize topological properties of networks that allow them to achieve the above diffusion objectives. We introduce a graph-theoretic property termed "robustness", and show that this plays a key role in the study of these dynamics. This property is much stronger than other classical graph properties such as connectivity and minimum degree, in that one can construct graphs with high connectivity and minimum degree but low robustness. However, we show that the nations of connectivity and robustness coincide on several common random graph models for complex networks (Erdos-Renyi, geometric random, and preferential attachment graphs). Specifically, robustness and connectivity share the same threshold function in the Erdos-Renyi model, cannot be very different in the geometric random graph model, and are equivalent in the preferential attachment model. This indicates that these networks gain a great deal of structure at their various thresholds, and facilitate the spreading of information via a variety of purely local diffusion dynamics.

Shreyas Sundaram is an Assistant Professor In the Department of Electrical and Computer Engineering at the University of Waterloo. He received his Ph.D. in Electrical Engineering from the University of Illinois at Urbana-Champaign in 2009, and was a Postdoctoral Researcher at the University of Pennsylvania from 2009 to 2010. His research interests include large-scale dynamical systems, network science, fault-tolerant and secure control, linear system and estimation theory, and the application of algebraic graph theory to system analysis. He received the M.E. Van Valkenburg Graduate Research Award and the Robert T. Chien Memorial Award from the University of Illinois, both for excellence in research. He was finalist for the Best Student Paper Award at the 2007 and 2008 American Control Conference.