Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
| Autor: | Shiping Liu, Fatihcan M. Atay |
|---|---|
| Přispěvatelé: | Atay, Fatihcan M. |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Bipartiteness 0102 computer and information sciences 02 engineering and technology Structural balance 01 natural sciences Theoretical Computer Science Combinatorics Mathematics - Spectral Theory 05C50 05C22 05C85 39A12 Computer Science - Data Structures and Algorithms Spectral clustering 0202 electrical engineering electronic engineering information engineering FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Invariant (mathematics) 10. No inequality Cluster analysis Signed graph Spectral Theory (math.SP) Eigenvalues and eigenvectors Mathematics Discrete mathematics Connected component Laplace transform Signed Laplace matrix Cheeger constant 020206 networking & telecommunications 16. Peace & justice 010201 computation theory & mathematics Combinatorics (math.CO) 05C50 Real projective space |
| Zdroj: | Discrete Mathematics |
| Popis: | 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, those measures of bipartiteness introduced by Desai-Rao, Trevisan, Bauer-Jost, respectively, on unsigned graphs,, and the frustration index (originally called the line index of balance by Harary) on signed graphs. We further unify the (higher-order or improved) Cheeger and dual Cheeger inequalities for unsigned graphs as well as the underlying algorithmic proof techniques by establishing their corresponding versions on signed graphs. In particular, we develop a spectral clustering method for finding $k$ almost-balanced subgraphs, each defining a sparse cut. The proper metric for such a clustering is the metric on a real projective space. We also prove estimates of the extremal eigenvalues of signed Laplace matrix in terms of number of signed triangles ($3$-cycles). Comment: We add more details for the proof of Lemma 6.4, Theorem 6.2, Theorem 6.3. We also explain more details about the control of those various absolute constant appearing in our estimates |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|