@inproceedings{119eae1fbc904a87948e8d03a373e732,
title = "Randomized consensus with attractive and repulsive links",
abstract = "We study convergence properties of a randomized consensus algorithm over a graph with both attractive and repulsive links. At each time instant, a node is randomly selected to interact with a random neighbor. Depending on if the link between the two nodes belongs to a given subgraph of attractive or repulsive links, the node update follows a standard attractive weighted average or a repulsive weighted average, respectively. The repulsive update has the opposite sign of the standard consensus update. In this way, it counteracts the consensus formation and can be seen as a model of link faults or malicious attacks in a communication network, or the impact of trust and antagonism in a social network. Various probabilistic convergence and divergence conditions are established. A threshold condition for the strength of the repulsive action is given for convergence in expectation: when the repulsive weight crosses this threshold value, the algorithm transits from convergence to divergence. An explicit value of the threshold is derived for classes of attractive and repulsive graphs. The results show that a single repulsive link can sometimes drastically change the behavior of the consensus algorithm. They also explicitly show how the robustness of the consensus algorithm depends on the size and other properties of the graphs.",
keywords = "Consensus algorithms, Gossiping, Opinion dynamics, Random networks, Sensor networks, Social networks",
author = "Guodong Shi and Alexandre Proutiere and Mikael Johansson and Johansson, {Karl H.}",
year = "2013",
doi = "10.1109/CDC.2013.6760274",
language = "English",
isbn = "9781467357173",
series = "Proceedings of the IEEE Conference on Decision and Control",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "2599--2604",
booktitle = "2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013",
address = "United States",
note = "52nd IEEE Conference on Decision and Control, CDC 2013 ; Conference date: 10-12-2013 Through 13-12-2013",
}