Detectability of the spectral method for sparse graph partitioning

Abstract

We show that modularity maximization with the resolution parameter offers a unifying framework of graph partitioning. In this framework, we demonstrate that the spectral method exhibits universal detectability, irrespective of the value of the resolution parameter, as long as the graph is partitioned. Furthermore, we show that when the resolution parameter is sufficiently small, a first-order phase transition occurs, resulting in the graph being unpartitioned.

6 pages, 2 figures

References in corpus (7)

• Modularity and community structure in networks
• Stochastic blockmodels and community structure in networks
• Graph spectra and the detectability of community structure in networks
• Parsimonious module inference in large networks
• (Un)detectable cluster structure in sparse networks
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Universal Phase Transition in Community Detectability under a Stochastic Block Model

Cited by in corpus (10)

• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Universality of the stochastic block model
• Super-resolution community detection for layer-aggregated multilayer networks
• Mean-field theory of graph neural networks in graph partitioning
• Algorithmic detectability threshold of the stochastic block model
• Comparative analysis on the selection of number of clusters in community detection
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Detectability thresholds of general modular graphs
• Consistency between ordering and clustering methods for graphs
• Fragility of spectral clustering for networks with an overlapping structure