A generalized Cheeger inequality
A generalized Cheeger inequality
复制标题
广义奇格不等式
DOI：
10.1016/j.laa.2023.01.014
复制
发表时间：
2023
影响因子：
1.1
通讯作者：
Peng, Richard
中科院分区：
文献类型：
--
作者：
Koutis, Ioannis;Miller, Gary;Peng, Richard
广义电导ϕ(G, H)两个加权图G和H在同一顶点集合V被定义为比ϕ(G, H) =分钟S⊆Vc p G (S, S¯)c p H (S, S¯),其中c p G (S, S¯)总重量是边缘交叉的顶点集合S⊆V S¯=−美国我们表明,最小广义特征值λ(L G L H)对拉普拉斯算子L G和L H满足ϕ(G, H)≥λ(L G L H)≥ϕ(G, H)ϕ(G) / 16日其中φ (G)是G的标准电导。满足这个界的广义割可以由λ (L G, L H)对应的广义特征向量得到。
The generalized conductance ϕ (G, H) between two weighted graphs G and H on the same vertex set V is defined as the ratio ϕ (G, H)= min S⊆ V c a p G (S, S¯) c a p H (S, S¯), where c a p G (S, S¯) is the total weight of the edges crossing from vertex set S⊆ V to S¯= V− S. We show that the minimum generalized eigenvalue λ (L G, L H) of the pair of Laplacians L G and L H satisfies ϕ (G, H)≥ λ (L G, L H)≥ ϕ (G, H) ϕ (G)/16, where ϕ (G) is the standard conductance of G. A generalized cut that meets this bound can be obtained from the generalized eigenvector corresponding to λ (L G, L H).