A Cheeger Inequality for Size-Specific Conductance
Provides theoretical foundations for a spectral method to optimize μ-conductance, which is useful for graph clustering and community detection in large networks.
The authors prove a Cheeger inequality for μ-conductance, a size-specific conductance measure, showing that the spectral relaxation of μ-conductance has a two-sided Cheeger inequality. This enables new ways to study network structures.
The $μ$-conductance measure proposed by Lovász and Simonovits is a size-specific conductance score that identifies the set with smallest conductance while disregarding those sets with volume smaller than a $μ$ fraction of the whole graph. Using $μ$-conductance enables us to study the network structures in new ways. In this manuscript we study a modified spectral cut for $μ$-conductance that is a natural relaxation of the integer program of $μ$-conductance and show that the optimum of this program has a two-sided Cheeger inequality with $μ$-conductance.