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

We consider an issue of much current concern: could fairness, an issue that is already difficult to guarantee, worsen when algorithms run much of our lives? We consider this in the context of resource-allocation problems; we show that algorithms can guarantee certain types of fairness in a verifiable way. Our conceptual contribution is a simple approach to fairness in this context, which only requires that all users trust some public lottery. Our technical contributions are in ways to address the $k$-center and knapsack-center problems that arise in this context: we develop a novel dependent-rounding technique that, via the new ingredients of "slowing down" and additional randomization, guarantees stronger correlation properties than known before. Read More


We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters $\beta$ (the interaction) and $\lambda$ (the external field), except for the case $\vert{\lambda}\vert=1$ (the "zero-field" case). A randomized algorithm (FPRAS) for all graphs, and all $\beta,\lambda$, has long been known. Read More


We study the shared processor scheduling problem with a single shared processor where a unit time saving (weight) obtained by processing a job on the shared processor depends on the job. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an $O(n \log n)$ optimization algorithm for a class of instances in which non-decreasing order of jobs with respect to processing times provides a non-increasing order with respect to weights --- this instance generalizes the unweighted case of the problem. Read More


Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Read More


A graph $G$ is equitably $k$-colorable if its vertices can be partitioned into $k$ independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest integer $k$ for which such a coloring exists is known as the \emph{equitable chromatic number} of $G$ and it is denoted by $\chi_{=}(G)$. In this paper the problem of determinig the value of equitable chromatic number for multicoronas of cubic graphs $G \circ^l H$ is studied. Read More


In 1947 Nathan Fine gave a beautiful product for the number of binomial coefficients $\binom{n}{m}$, for $m$ in the range $0 \leq m \leq n$, that are not divisible by $p$. We give a matrix product that generalizes Fine's formula, simultaneously counting binomial coefficients with $p$-adic valuation $\alpha$ for each $\alpha \geq 0$. For each $n$ this information is naturally encoded in a polynomial generating function, and the sequence of these polynomials is $p$-regular in the sense of Allouche and Shallit. Read More


Partly in service of exploring the formal basis for Georgetown University's AvesTerra database structure, we formalize a recursive hypergraph data structure, which we call an ubergraph. Read More


The generalized hierarchical product of graphs was introduced by L. Barri\'ere et al in 2009. In this paper, reformulated first Zagreb index of generalized hierarchical product of two connected graphs and hence as a special case cluster product of graphs are obtained. Read More


Not all approximations arise from information systems. The problem of fitting approximations, subjected to some rules (and related data), to information systems in a rough scheme of things is known as the \emph{inverse problem}. The inverse problem is more general than the duality (or abstract representation) problems and was introduced by the present author in her earlier papers. Read More