  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\leq i \leq m$,
otherwise the distribution of edges is $q_i=\beta_i\log{n}/n$ for $1\leq i \leq
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.
