Speaker: Shreyas Sundaram
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 neighbours’ 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 neighbourhood. 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 behaviour 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 behaviour. He then shows that several common random graph models for complex networks exhibit a threshold behaviour for robustness, and that well-connected complex networks also tend to be highly robust (a much stronger property).