Friend or Foe? Population Protocols can perform Community Detection

We present a simple distributed algorithm that, given a regular graph consisting of two communities (or clusters), each inducing a good expander and such that the cut between them has sparsity $1/\mbox{polylog}(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, for all but a small number of outliers, nodes within the same community are assigned labels with Hamming distance $o(m)$, while nodes belonging to different communities receive labels with Hamming distance at least $m/2 - o(m)$. We refer to such an outcome as a "community sensitive labeling" of the graph. Our algorithm uses $\Theta(\log^2 n)$ local memory and computes the community sensitive labeling after each node performs $\Theta(\log^2 n)$ steps of local work. Our algorithm and its analysis work in the "(random) population protocol" model, in which anonymous nodes do not share any global clock (the model is asynchronous) and communication occurs over one single (random) edge per round. We believe, this is the first provably-effective protocol for community detection that works in this model.

Comments: 26 pages

Similar Publications

A common task in phylogenetics is to find an evolutionary tree representing proximity relationships between species. This motivates the notion of leaf powers: a graph G = (V, E) is a leaf power if there exist a tree T on leafset V and a threshold k such that uv is an edge if and only if the distance between u and v in T is at most k. Characterizing leaf powers is a challenging open problem, along with determining the complexity of their recognition. Read More


We introduce and study the game of Selfish Cops and Adversarial Robber (SCAR) which is an N-player generalization of the classic two-player cops and robbers (CR) game. We prove that SCAR has a Nash equilibrium in deterministic strategies. Read More


These lecture notes are on automorphism groups of Cayley graphs and their applications to optimal fault-tolerance of some interconnection networks. We first give an introduction to automorphisms of graphs and an introduction to Cayley graphs. We then discuss automorphism groups of Cayley graphs. Read More


We define a special case of tree decompositions for planar graphs that respect a given embedding of the graph. We study the analogous width of the resulting decomposition we call the embedded-width of a plane graph. We show both upper bounds and lower bounds for the embedded-width of a graph in terms of its treewidth and describe a fixed parameter tractable algorithm to calculate the embedded-width of a plane graph. Read More


Abelian cellular automata (CA) are CA which are group endomorphisms of the full group shift when endowing the alphabet with an abelian group structure. A CA randomizes an initial probability measure if its iterated images weak *-converge towards the uniform Bernoulli measure (the Haar measure in this setting). We are interested in structural phenomena, i. Read More


Gottschalk and Vygen proved that every solution of the well-known subtour elimination linear program for traveling salesman paths is a convex combination of a set of more and more restrictive "generalized Gao trees" of the underlying graph. In this paper we give a short proof of this, as a {\em layered} convex combination of bases of a sequence of more and more restrictive matroids. Our proof implies (via the matroid partition theorem) a strongly-polynomial combinatorial algorithm for finding this convex combination. Read More


In a graph, a Clique-Stable Set separator (CS-separator) is a family $\mathcal{C}$ of cuts (bipartitions of the vertex set) such that for every clique $K$ and every stable set $S$ with $K \cap S = \emptyset$, there exists a cut $( W,W')$ in $\mathcal{C}$ such that $K \subseteq W$ and $S \subseteq W'$. Starting from a question concerning extended formulations of the Stable Set polytope and a related complexity communication problem, Yannakakis [17] asked in 1991 the following questions: does every graph admit a polynomial-size CS-separator? If not, does every perfect graph do? Several positive and negative results related to this question were given recently. Here we show how graph decomposition can be used to prove that a class of graphs admits a polynomial CS-separator. Read More


We consider the modeling approach introduced by R. Thomas for the qualitative study of gene regulatory networks. Tools and results on regulatory networks are often concerned only with the Boolean case of this formalism. Read More


We prove a Gauss-Bonnet formula X(G) = sum_x K(x), where K(x)=(-1)^dim(x) (1-X(S(x))) is a curvature of a vertex x with unit sphere S(x) in the Barycentric refinement G1 of a simplicial complex G. K(x) is dual to (-1)^dim(x) for which Gauss-Bonnet is the definition of Euler characteristic X. Because the connection Laplacian L'=1+A' of G is unimodular, where A' is the adjacency matrix of of the connection graph G', the Green function values g(x,y) = (1+A')^-1_xy are integers and 1-X(S(x))=g(x,x). Read More


In this work we investigate the problem of order batching and picker routing in storage areas. These are labour and capital intensive problems, often responsible for a substantial share of warehouse operating costs. In particular, we consider the case of online grocery shopping in which orders may be composed of dozens of items. Read More