Robustness of Complex Networks: Reaching Agreement Despite Stubborn and Malicious Adversaries

There has been a great deal of research devoted to the study of information diffusion in complex networks. These investigations have revealed that certain structural properties and dynamics allow information held by a few individuals to quickly spread throughout the network. While this is beneficial when the information originates at trustworthy nodes, it also indicates that certain networks may be susceptible to disruption by malicious, stubborn, or extreme individuals. Thus, a fundamental challenge is to identify structural properties and diffusion dynamics that allow legitimate information to propagate throughout the network, while limiting the effects of illegitimate individuals and actions.

The goal of this research project is to study a special case of information diffusion where all nodes in the network synchronize (or reach agreement) on some parameter of interest. We focus 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, we study a natural class of dynamics where each normal node views its neighbors’ values with suspicion, and 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, we develop a new topological property that we term “robustness”, and show that graphs with a sufficient degree of robustness can tolerate a variety of adversarial behavior. We also show that several common random graph models for complex networks exhibit a phase-transition behavior for robustness, and that well-connected complex networks also tend to be highly robust (a much stronger property).

Download a copy of the technical report to WICI detailing the research project’s findings here.

Papers arising from the research:

H. Zhang and S. Sundaram, “Robustness of Information Diffusion Algorithms to Locally Bounded Adversaries”, Proceedings of the 2012 American Control Conference. Preprint available at:http://arxiv.org/abs/1110.3843

H. LeBlanc, H. Zhang, S. Sundaram and X. Koutsoukos, “Consensus of Multi-Agent Networks in the Presence of Adversaries Using Only Local Information”, Proceedings of the First Conference on High Confidence Networked Systems (HiCoNS) at CPSWeek 2012. Available at: http://cps-vo.org/node/2512

H. Zhang and S. Sundaram, “Robustness of Complex Networks: Reaching Consensus Despite Adversaries”, Preprint available at:http://arxiv.org/abs/1203.6119