Phase Transitions in Spectral Community Detection

Abstract

Consider a network consisting of two subnetworks (communities) connected by some external edges. Given the network topology, the community detection problem can be cast as a graph partitioning problem that aims to identify the external edges as the graph cut that separates these two subnetworks. In this paper, we consider a general model where two arbitrarily connected subnetworks are connected by random external edges. Using random matrix theory and concentration inequalities, we show that when one performs community detection via spectral clustering there exists an abrupt phase transition as a function of the random external edge connection probability. Specifically, the community detection performance transitions from almost perfect detectability to low detectability near some critical value of the random external edge connection probability. We derive upper and lower bounds on the critical value and show that the bounds are equal to each other when two subnetwork sizes are identical. Using simulated and experimental data we show how these bounds can be empirically estimated to validate the detection reliability of any discovered communities.

9 pages, 4 figures, submitted to IEEE Trans. on Signal Processing. arXiv admin note: text overlap with arXiv:1504.02412

References in corpus (8)

• Modularity and community structure in networks
• Stochastic blockmodels and community structure in networks
• Discrete Signal Processing on Graphs
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• Network histograms and universality of blockmodel approximation
• A paradox in community detection
• Universal Phase Transition in Community Detectability under a Stochastic Block Model

Cited by in corpus (9)

• Super-resolution community detection for layer-aggregated multilayer networks
• Signal Representations on Graphs: Tools and Applications
• Bias-Variance Tradeoff of Graph Laplacian Regularizer
• Incremental Method for Spectral Clustering of Increasing Orders
• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• Clustering and Community Detection with Imbalanced Clusters
• AMOS: An Automated Model Order Selection Algorithm for Spectral Graph Clustering
• Revisiting Spectral Graph Clustering with Generative Community Models
• Incremental Eigenpair Computation for Graph Laplacian Matrices: Theory and Applications