Computer Science – Social and Information Networks
Scientific paper
2012-03-28
Computer Science
Social and Information Networks
Preprint of paper submitted to the 2012 Conference on Decision and Control
Scientific paper
We study the problem of reaching consensus in complex networks where each node knows nothing about the overall topology, other than its own neighbors. We assume that there exist a set of malicious or stubborn nodes in the network that do not follow the same dynamics as the rest of the nodes. When the normal nodes act on purely local information, previous work has established that standard graph notions such as connectivity are no longer sufficient to characterize the ability of the non-malicious nodes to reach agreement. Instead, the network must satisfy a property known as robustness. In this paper we investigate the robustness properties of common random graph models for complex networks, including the preferential attachment model, the Erdos-Renyi model, and the geometric random graph model. We show that these models exhibit a thresholding behavior for robustness. In particular, we show that the notions of connectivity and robustness coincide on various random graph models, indicating that purely local knowledge is sufficient when the objective is to reach agreement on an appropriate function of the initial values.
Sundaram Shreyas
Zhang Haotian
No associations
LandOfFree
Robustness of Complex Networks: Reaching Consensus Despite Adversaries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Robustness of Complex Networks: Reaching Consensus Despite Adversaries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robustness of Complex Networks: Reaching Consensus Despite Adversaries will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-271412