Community Detection with Colored Edges

Original · EN

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ᵢ=αᵢn/n for 1≤ i ≤ m, otherwise the distribution of edges is qᵢ=βᵢn/n for 1≤ i ≤ m, where αᵢ and βᵢ 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 ∑ᵢ₌₁ᵐ (√αᵢ - √βᵢ)² >2, then the community detection via maximum likelihood (ML) estimator is possible with high probability. If ∑ᵢ₌₁ᵐ (√αᵢ - √βᵢ)² < 2, the probability that the ML estimator fails to detect the communities does not go to zero.