Speaker: Shreyas Sundaram
Title: Reaching Agreement in Complex Networks: Avoiding the Influence of Extreme Agents
Date: Tuesday, March 20th, 2012
Professor Shreyas Sundaram describes a special case of information diffusion where all nodes in the network synchronize (or reach agreement) on some parameter of interest. He focuses on a class of diffusion dynamics where the state of each node is continually updated as a weighted average of its neighbors’ states. When all nodes follow these dynamics, one can prove that their states will converge to a common value. However, these dynamics are also easily hijacked by malicious or stubborn individuals that wish to bias the consensus value. To mitigate the influence of malicious nodes, he describes a natural extension to these dynamics where each normal node disregards the most extreme states in its neighborhood. While this local rule is simple to state, it turns out that traditional graph theoretic metrics (such as connectivity) are no longer sufficient to characterize the global behavior of this class of dynamics. Instead, he describes a new topological property termed “robustness”, and show that graphs with a sufficient degree of robustness can tolerate a variety of malicious behavior. He then shows that several common random graph models for complex networks exhibit a threshold behavior for robustness, and that well-connected complex networks also tend to be highly robust (a much stronger property).