Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433878 | Theoretical Computer Science | 2015 | 23 Pages |
Inspired by the increasing interest in self-organizing social opportunistic networks, we investigate the problem of distributed detection of unknown communities in dynamic random graphs. As a formal framework, we consider the dynamic version of the well-studied Planted Bisection Model dyn-G(n,p,q)dyn-G(n,p,q) where the node set [n][n] of the network is partitioned into two unknown communities and, at every time step, each possible edge (u,v)(u,v) is active with probability p if both nodes belong to the same community, while it is active with probability q (with q≪pq≪p) otherwise. We also consider a time-Markovian generalization of this model.We propose a distributed protocol based on the popular Label-Propagation approach and prove that, when the ratio p/qp/q is larger than nbnb (for an arbitrarily small constant b>0b>0), the protocol finds the right “planted” partition in O(logn)O(logn) time even when the snapshots of the dynamic graph are sparse and disconnected (i.e., when p=Θ(1/n)p=Θ(1/n)).