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.
이 논문에서는 여러 종류의 연결을 가지는 그래프에서의 커뮤니티 검출 한계를 증명하였다. 이를 위해 우리는 다음과 같은 모델을 가정하였다. 먼저, 그래프 내에 같은 수의 노드로 이루어진 커뮤니티 2개가 있고, 노드 간에는 $m $개의 서로 다른 종류의 연결이 존재한다. 만약 두 노드가 같은 커뮤니티에 있다면, 그 노드들 간의 연결은 $1\leq i \leq m$ 를 만족하는 $i$ 에 대해 $p_i=\alpha_i\log{n}/n$의 분포를 따르며, 두 노드가 다른 커뮤니티에 있다면 $q_i=\beta_i\log{n}/n$ 의 분포를 따른다. 여기서 $\alpha_i$ 와 $\beta_i$ 는 양수이며 $n$ 은 그래프 안에 존재하는 노드의 개수이다. 이러한 가정을 했을 때, 커뮤니티 검출 한계는 두 확률 분포 간의 헬링거 거리로 다음과 같이 표현될 수 있다. 만약 어떤 그래프가 $\sum_{i=1}^{m} {(\sqrt{\alpha_{i}}-\sqrt{\beta_{i}})}^{2}>2$ 를 만족한다면, 최대 가능도 방법을 통해 높은 확률로 커뮤니티 검출이 가능하다. 또한 $\sum_{i=1}^{m} {(\sqrt{\alpha_{i}}-\sqrt{\beta_{i}})}^{2}<2$ 를 만족한다면, 최대 가능도 방법을 사용하여도 커뮤니티 검출이 불가능할 확률이 0이 되지 않는다.
