Community Detection with Colored Edges

Abstract

In this paper, we prove a sharp limit on the community detection problem with colored edges. We assume two equal-sized communities and there are $m$ different types of edges. If two vertices are in the same community, the distribution of edges follows $p_i={\alpha }_i\log n/n$ for $1\le i\le m$, otherwise the distribution of edges is $q_i={\beta }_i\log n/n$ for $1\le i\le m$, where ${\alpha }_i$ and ${\beta }_i$ are positive constants and $n$ is the total number of vertices. Under these assumptions, a fundamental limit on community detection is characterized using the Hellinger distance between the two distributions. If ${\sum }_{i=1}^m{(\sqrt{{\alpha }_i}-\sqrt{{\beta }_i})}^2>2$, then the community detection via maximum likelihood (ML) estimator is possible with high probability. If ${\sum }_{i=1}^m{(\sqrt{{\alpha }_i}-\sqrt{{\beta }_i})}^2<2$, the probability that the ML estimator fails to detect the communities does not go to zero.

The material in this paper was presented in part at the IEEE International Symposium on Information Theory (ISIT) 2016