We study a Plurality Consensus process in which each of n anonymous agents of a communication network supports an initial opinion (a color chosen from a finite set [k]) and, at every time step, he can revise his color according to a random sample of neighbors. The goal (of the agents) is to let the process converge to the stable configuration where all nodes support the plurality color. It is assumed that the initial color configuration has a sufficiently large bias s, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by an additive value s. We consider a basic model in which the network is a clique and the update rule (called here the 3-majority dynamics) of the process is that each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly at random). We prove a tight bound on the convergence time which grows as ⊖(k log n) for a wide range of parameters k and n. This linear-in-k dependence implies an exponential timegap between the plurality consensus process and the median process studied in [7]. A natural question is whether looking at more (than three) random neighbors can significantly speed up the process. We provide a negative answer to this question: in particular, we show that samples of polylogarithmic size can speed up the process by a polylogarithmic factor only.

Simple dynamics for Plurality Consensus / Becchetti, Luca; Andrea E. F., Clementi; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo; Luca, Trevisan. - STAMPA. - (2014), pp. 247-256. (Intervento presentato al convegno 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2014 tenutosi a Prague nel 23 June 2014 through 25 June 2014) [10.1145/2612669.2612677].

Simple dynamics for Plurality Consensus

BECCHETTI, Luca;NATALE, EMANUELE;PASQUALE, FRANCESCO;SILVESTRI, RICCARDO;
2014

Abstract

We study a Plurality Consensus process in which each of n anonymous agents of a communication network supports an initial opinion (a color chosen from a finite set [k]) and, at every time step, he can revise his color according to a random sample of neighbors. The goal (of the agents) is to let the process converge to the stable configuration where all nodes support the plurality color. It is assumed that the initial color configuration has a sufficiently large bias s, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by an additive value s. We consider a basic model in which the network is a clique and the update rule (called here the 3-majority dynamics) of the process is that each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly at random). We prove a tight bound on the convergence time which grows as ⊖(k log n) for a wide range of parameters k and n. This linear-in-k dependence implies an exponential timegap between the plurality consensus process and the median process studied in [7]. A natural question is whether looking at more (than three) random neighbors can significantly speed up the process. We provide a negative answer to this question: in particular, we show that samples of polylogarithmic size can speed up the process by a polylogarithmic factor only.
2014
26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2014
general markov chains; markov chains; parallel randomized algorithms; plurality consensus
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Simple dynamics for Plurality Consensus / Becchetti, Luca; Andrea E. F., Clementi; Natale, Emanuele; Pasquale, Francesco; Silvestri, Riccardo; Luca, Trevisan. - STAMPA. - (2014), pp. 247-256. (Intervento presentato al convegno 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2014 tenutosi a Prague nel 23 June 2014 through 25 June 2014) [10.1145/2612669.2612677].
File allegati a questo prodotto
File Dimensione Formato  
VE_2014_11573-610617.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 634.21 kB
Formato Adobe PDF
634.21 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/610617
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? ND
social impact