Robustness of Information Diffusion Dynamics in Complex Networks

Event Date: April 21, 2014
Speaker: Shreyas Sundaram
Speaker Affiliation: University of Waterloo
Time: 10:30am, Reception 11:30am
Location: EE 317
Contact Name: Jianghu Hu
Contact Phone: 765-496-2395
Contact Email: jianghai@purdue.edu

Abstract

Complex networks are prevalent in both the natural world (e.g., ecological, biological, and social systems), and in engineered applications (e.g., the Internet, the power grid, and large-scale sensor networks).  A key metric of interest in the study of such networks is their robustness to disruptions, both in the structure and in the dynamics that are occurring on the network.

In this talk, I describe some recent results on the robustness of information diffusion dynamics in networks.  First, I show how tools from linear system theory, structured system theory and graph theory can be applied to analyze a class of linear diffusion dynamics.  When the correctly functioning nodes know the network topology, I show that the connectivity of the network (i.e., the number of disjoint paths in the network between any two nodes) is the key factor that determines the resilience of such linear dynamics to a certain number of adversarial nodes that behave in arbitrary ways. This provides a dynamical systems perspective on the role of connectivity as a metric of network robustness.  Next, I consider a class of opinion dynamics where each node in the network disregards its most extreme neighbors and updates its opinion as a weighted average of the remaining opinions.  I show that connectivity is no longer a sufficiently powerful metric to characterize the convergence of this natural class of dynamics, and instead introduce a quantifiable graph-theoretic property termed "robustness".  This property is much stronger than classical graph properties such as connectivity, in that one can construct graphs with high connectivity but low robustness. However, I show that the notions of connectivity and robustness coincide in 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, and are equivalent in 1-D geometric graphs and certain preferential attachment networks.  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.

Biography

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.  He was a Postdoctoral Researcher at the University of Pennsylvania from 2009 to 2010 and a Visiting Assistant Professor at Boston University in 2013.  He received the University of Waterloo Outstanding Performance Award in 2013 and the Waterloo Faculty of Engineering Distinguished Performance Award in 2012.  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, and he was a finalist for the Best Student Paper Award at the 2007 and 2008 American Control Conferences.  His research interests include network science, large-scale dynamical systems, fault-tolerant and secure control, linear system and estimation theory, and the application of algebraic graph theory to system analysis.