Notiziario Scientifico
Settimana dal 21 al 27 luglio 2014
Mercoledì 23 luglio 2014
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.
Ore 15:00, Aula 211, Università di Roma III
Seminario di Probabilità
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.
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.