Notiziario Scientifico

Settimana dal 21 al 27 luglio 2014


Mercoledì 23 luglio 2014
Ore 15:00, Aula 211, Università di Roma III
Seminario di Probabilità
Andrea Clementi (Università di Roma II)
Simple Dynamics for Plurality Consensus
AUTHORS: L. Becchetti, A. Clementi, E. Natale, F. Pasquale, R. Silvestri, and L. Trevisan We study a Majority 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. It is assumed that the initial color configuration has a sufficiently large emph[bias] s towards a fixed majority color, that is, the number of nodes supporting the majority color exceeds the number of nodes supporting any other color by s additional nodes.The goal (of the agents) is to let the process converge to the emph[stable] configuration where all nodes support the majority color. We consider a basic model in which the network is a clique and the update rule (called here the emph[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). We prove that the process converges in time mathcal[O]left(min[ k, (n/log n)^[1/3] ] , log n ight) with high probability, provided that s geqslant c sqrt[ min[ 2k, (n/log n)^[1/3] ], n log n].Departing significantly from the previous analysis, our proof technique also yields a polylog(n) bound on the convergence time whenever the initial number of nodes supporting the majority color is larger than n/polylog (n) and s geqslant sqrt[n , polylog (n)], emph[no matter how large] k emph[is]. We then prove that our upper bound above is tight as long as k leqslant (n/log n)^[1/4]. This fact implies an exponential time-gap between the majority-consensus process and the emph[median] process studied in~cite[DGMSS11]. smallskip 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.


Tutte le informazioni relative a questo notiziario devono pervenire all'indirizzo di posta elettronica seminari@mat.uniroma1.it entro le ore 9 del venerdì precedente la settimana di pubblicazione.

Tutti coloro che desiderano ricevere questo notiziario via e-mail sono invitati a comunicare il proprio indirizzo di posta elettronica a seminari@mat.uniroma1.it.

                Il Direttore

Il calendario dei seminari è anche disponibile su internet.

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma