How agreement and disagreement evolve over random dynamic networks
2013 (English)In: IEEE Journal on Selected Areas in Communications, ISSN 0733-8716, E-ISSN 1558-0008, Vol. 31, no 6, 1061-1071 p.Article in journal (Refereed) Published
The dynamics of an agreement protocol interacting with a disagreement process over a common random network is considered. The model can represent the spreading of true and false information over a communication network, the propagation of faults in a large-scale control system, or the development of trust and mistrust in a society. At each time instance and with a given probability, a pair of network nodes interact. At random each of the nodes then updates its state towards the state of the other node (attraction), away from the other node (repulsion), or sticks to its current state (neglect). Agreement convergence and disagreement divergence results are obtained for various strengths of the updates for both symmetric and asymmetric update rules. Impossibility theorems show that a specific level of attraction is required for almost sure asymptotic agreement and a specific level of repulsion is required for almost sure asymptotic disagreement. A series of sufficient and/or necessary conditions are then established for agreement convergence or disagreement divergence. In particular, under symmetric updates, a critical convergence measure in the attraction and repulsion update strength is found, in the sense that the asymptotic property of the network state evolution transits from agreement convergence to disagreement divergence when this measure goes from negative to positive. The result can be interpreted as a tight bound on how much bad action needs to be injected in a dynamic network in order to consistently steer its overall behavior away from consensus.
Place, publisher, year, edition, pages
2013. Vol. 31, no 6, 1061-1071 p.
Consensus algorithms, Dynamic networks, Gossiping, Network science, Opinion dynamics, Social networks, Dynamic network, Communication, Telecommunication networks
Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-134451DOI: 10.1109/JSAC.2013.130608ISI: 000319353900008ScopusID: 2-s2.0-84878129504OAI: oai:DiVA.org:kth-134451DiVA: diva2:676218
FunderKnut and Alice Wallenberg FoundationSwedish Research CouncilICT - The Next Generation
QC 201312052013-12-052013-11-252014-09-19Bibliographically approved