Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
111/2014

Cheeger constants, structural balance, and spectral clustering analysis for signed graphs

Fatihcan M. Atay and Shiping Liu

Abstract

We introduce a family of multi-way Cheeger-type constants $\{h_k^{\sigma}, k=1,2,\ldots, N\}$ on a signed graph $\Gamma=(G,\sigma)$ such that $h_k^{\sigma}=0$ if and only if $\Gamma$ has $k$ balanced connected components. These constants are switching invariant and bring together in a unified viewpoint a number of important graph-theoretical concepts, including the classical Cheeger constant, the non-bipartiteness parameter of Desai and Rao, the bipartiteness ratio of Trevisan, the dual Cheeger constant of Bauer and Jost on unsigned graphs, and the line index of imbalance of Harary (also called the frustration index) on signed graphs.

We then propose a corresponding spectral clustering algorithm for finding $k$ almost-balanced subgraphs, each defining a sparse cut. We find that the proper metric for the clustering algorithm is the metric on a real projective space. Remarkably, this algorithm includes the traditional spectral clustering algorithm on unsigned graphs via spherical metrics as a special case. We verify the algorithm theoretically by proving higher-order signed Cheeger inequalities, and signed improved Cheeger inequalities concerning higher-order spectral gaps.

We also prove estimates of the extremal eigenvalues of signed Laplace matrix in terms of number of signed triangles (3-cycles).

Received:
13.11.14
Published:
20.11.14
MSC Codes:
05C50, 05C22, 05C85

Related publications

inJournal
2020 Repository Open Access
Fatihcan M. Atay and Shiping Liu

Cheeger constants, structural balance, and spectral clustering analysis for signed graphs

In: Discrete mathematics, 343 (2020) 1, p. 111616