Randomized consensus with attractive and repulsive links
2013 (English)In: 2013 IEEE 52nd Annual Conference on Decision and Control (CDC), IEEE conference proceedings, 2013, 2599-2604 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
IEEE conference proceedings, 2013. 2599-2604 p.
, IEEE Conference on Decision and Control. Proceedings, ISSN 0743-1546
Consensus algorithms, Gossiping, Opinion dynamics, Random networks, Sensor networks, Social networks
IdentifiersURN: urn:nbn:se:kth:diva-151000DOI: 10.1109/CDC.2013.6760274ISI: 000352223503005ScopusID: 2-s2.0-84902344247ISBN: 978-1-4673-5714-2OAI: oai:DiVA.org:kth-151000DiVA: diva2:746238
52nd IEEE Conference on Decision and Control, CDC 2013, 10 December 2013 through 13 December 2013, Florence, Italy
QC 201409122014-09-122014-09-122015-12-08Bibliographically approved