Diffusing Information and Reaching Agreement in Networks: Convergence and Resilience

When: Wednesday, November 14, 2012 at 3:00 pm
Where: DA 5th fl
Speaker: DR. Shreyas Sundaram
Organization: Department of Electrical and Computer Engineering, University of Waterloo
Sponsor: CCNR Seminar

A key metric in the study of information diffusion mechanisms in networks is their resilience to adversarial or stubborn individuals. In this talk we consider a simple linear iterative strategy for information diffusion, where each node periodically updates its state as a linear combination of its neighbors’ states. When all nodes know the network topology, we use tools from structured system theory to show that this strategy can reliably diffuse information despite the actions of a bounded number of adversaries, as long as the network connectivity is sufficiently large. We then describe a modification to this strategy where each node first removes extreme values from its neighborhood, and then updates its value as a weighted average of the remaining values. We show that traditional graph metrics such as connectivity are no longer sufficient to analyze such dynamics, and introduce a new property called “robustness”. We show that sufficiently robust networks allow the nodes to reach consensus resiliently, without knowing anything about the global topology. This new property is much stronger than connectivity in that one can construct graphs with high connectivity but low robustness. However, we show that connectivity and robustness share the same threshold function in Erdos-Renyi random graphs, cannot be very different in geometric random graphs, and are equivalent in preferential attachment graphs. 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.