Community Detection: Exact Recovery in Weighted Graphs
This work provides theoretical conditions for exact community recovery in weighted graphs, which is important for researchers and practitioners working with real-world networks where edge weights carry meaningful information.
This paper investigates the exact recovery of communities in weighted graphs where edge weights are drawn from either Gaussian or exponential distributions. It introduces a new semi-metric that provides asymptotically tight necessary and sufficient conditions for exact recovery in both complete and incomplete fully connected weighted graphs.
In community detection, the exact recovery of communities (clusters) has been mainly investigated under the general stochastic block model with edges drawn from Bernoulli distributions. This paper considers the exact recovery of communities in a complete graph in which the graph edges are drawn from either a set of Gaussian distributions with community-dependent means and variances, or a set of exponential distributions with community-dependent means. For each case, we introduce a new semi-metric that describes sufficient and necessary conditions of exact recovery. The necessary and sufficient conditions are asymptotically tight. The analysis is also extended to incomplete, fully connected weighted graphs.