Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians

Abstract

We discuss a Cheeger constant as a mixture of the frustration index and the expansion rate, and prove the related Cheeger inequalities and higher order Cheeger inequalities for graph Laplacians with cyclic signatures, discrete magnetic Laplacians on finite graphs and magnetic Laplacians on closed Riemannian manifolds. In this process, we develop spectral clustering algorithms for partially oriented graphs and multi-way spectral clustering algorithms via metrics in lens spaces and complex projective spaces. As a byproduct, we give a unified viewpoint of Harary's structural balance theory of signed graphs and the gauge invariance of magnetic potentials.

30 pages, 4 figures. Section 5 is rewritten. Revised thanks to referee's suggestions

Cited by in corpus (10)

• Magnetic eigenmaps for community detection in directed networks
• Magnetic Eigenmaps for the Visualization of Directed Networks
• Curvature and higher order Buser inequalities for the graph connection Laplacian
• Spectral preorder and perturbations of discrete weighted graphs
• Higher-order Connection Laplacians for Directed Simplicial Complexes
• Matching number, Hamiltonian graphs and discrete magnetic Laplacians
• A geometric construction of isospectral magnetic graphs
• Heterogeneous networks for phase-sensitive engineering of optical disordered materials
• Evaluating balance on social networks from their simple cycles
• Geometric and spectral analysis on weighted digraphs