Distributed Community Detection in Dynamic Graphs
arXiv:1302.5607 · doi:10.1007/978-3-319-03578-9_1
Abstract
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 \emph{Planted Bisection Model} $\sdG(n,p,q)$ where the node set of the network is partitioned into two unknown communities and, at every time step, each possible edge is active with probability if both nodes belong to the same community, while it is active with probability (with ) otherwise. We also consider a time-Markovian generalization of this model. We propose a distributed protocol based on the popular \emph{Label Propagation Algorithm} and prove that, when the ratio is larger than (for an arbitrarily small constant ), the protocol finds the right "planted" partition in time even when the snapshots of the dynamic graph are sparse and disconnected (i.e. in the case ).
arXiv commentVersion II
References in corpus (11)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Hierarchical organization of modularity in metabolic networks
- Near linear time algorithm to detect community structures in large-scale networks
- The spread of epidemic disease on networks
- Comparing community structure identification
- Detecting network communities by propagating labels under constraints
- Advanced modularity-specialized label propagation algorithm for detecting communities in networks
- Stochastic Block Models and Reconstruction
- Performance of Opportunistic Epidemic Routing on Edge-Markovian Dynamic Graphs
- Distributed Community Detection in Dynamic Graphs