Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
复制标题
DOI：
10.1016/j.disc.2019.111616
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
F. Atay;Shiping Liu
中科院分区：
文献类型：
--
作者：
F. Atay;Shiping Liu
在有号图Γ=（G，σ）上引入了一类多路Cheeger型常数{hk σ，k= 1，2，.，n}，使得hk σ= 0当且仅当Γ有k个平衡连通分支.这些常数是开关不变的，并在一个统一的观点汇集了一些重要的图论概念，包括经典的Cheeger常数，这些措施的二分性介绍了德赛-饶，Trevisan，鲍尔-约斯特，分别对无符号图，和挫折指数（最初称为线指数的平衡由Harary）的签署图。我们进一步统一（高阶或改进）Cheeger和双Cheeger不等式的无符号图，以及底层的算法证明技术，通过建立相应的版本上签署的图。特别是，我们开发了一个谱聚类方法，找到k几乎平衡的子图，每个定义一个稀疏削减。这种聚类的适当度量是真实的射影空间上的度量。我们还证明了符号拉普拉斯矩阵的极值特征值的估计，根据的符号三角形（3-圈）的数量。
We introduce a family of multi-way Cheeger-type constants {h k σ, k= 1, 2,…, n} on a signed graph Γ=(G, σ) such that h k σ= 0 if and only if Γ 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).