max planck institut
informatik

MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Friend or foe? Population Protocols for Community Sensitive Labeling Luca Becchetti Sapienze University of Rome AG1 Mittagsseminar (own work) D1We use this to send out email in the morning. AG Audience English
Date: Thursday, 16 February 2017 13:00 30 Minutes Saarbrücken E1 4 - MPI-INF 024
 We present a simple distributed algorithm that, given a regular graph made of two communities (or clusters) such that each community induces a good expander and the cut between the two communities has sparsity $1/poly\log n$, recovers the two communities. More precisely, upon running the protocol, every node assigns itself a binary label of $m= \Theta(\log n)$ bits, so that with high probability, except for a small number of outlier nodes, nodes in the same community have labels of Hamming distance $o(m)$, while nodes in different communities have labels of Hamming distance at least $m/2 -o(m)$. We refer to such an outcome as a {\em community-sensitive labeling} of the graph. The algorithm uses $\Theta(\log^2 n)$ local memory and converges after each node makes $\Theta(\log^2 n)$ steps of local work. In an asynchronous model in which each node is activated by an independent Poisson clock with average one, the protocol converges with high probability in time $\Theta(\log^2 n)$. Our algorithm and its analysis work for the \emph{(random) population protocol} model, where anonymous nodes do not share any global clock (the model is asynchronous) and communication takes place over one single (random) edge per round. We believe that this is the first provably-effective protocols for community detection that works in this model.
Name(s): Emanuele Natale enatale@mpi-inf.mpg.de