THE FIEDLER VECTOR OF A LAPLACIAN TENSOR FOR HYPERGRAPH PARTITIONING
THE FIEDLER VECTOR OF A LAPLACIAN TENSOR FOR HYPERGRAPH PARTITIONING
复制标题
用于超图划分的拉普拉斯张量的费德勒向量
DOI：
10.1137/16m1094828
复制
发表时间：
2017-01-01
影响因子：
3.1
通讯作者：
Zhang, Xiaoyan
中科院分区：
文献类型：
--
作者：
Chen, Yannan;Qi, Liqun;Zhang, Xiaoyan
基于谱超图理论的最新进展[L. Qi和Z.罗，张量分析：Spectral Theory and Special Tensors，SIAM，Philadelphia，2017]，我们探索了偶均匀超图的Fiedler向量，它是与超图产生的归一化拉普拉斯张量的第二小Z特征值相关联的Z特征向量。然后，我们开发了一种新的基于张量的谱方法划分超图的顶点。为此，我们将简单图的正规化拉普拉斯矩阵推广到偶均匀超图的正规化拉普拉斯张量。相应的Fiedler向量与超图的Cheeger常数有关。然后，我们建立了一个可行的优化算法计算Fiedler向量根据归一化拉普拉斯张量。从理论上分析了算法的收敛性和获得超图Fiedler向量的概率。最后，初步的数值实验表明，新的方法是可行的。
Based on recent advances in spectral hypergraph theory [L. Qi and Z. Luo, Tensor Anaysis: Spectral Theory and Special Tensors, SIAM, Philadelphia, 2017], we explore the Fiedler vector of an even-uniform hypergraph, which is the Z-eigenvector associated with the second smallest Z-eigenvalue of a normalized Laplacian tensor arising from the hypergraph. Then, we develop a novel tensor-based spectral method for partitioning vertices of the hypergraph. For this purpose, we extend the normalized Laplacian matrix of a simple graph to the normalized Laplacian tensor of an even-uniform hypergraph. The corresponding Fiedler vector is related to the Cheeger constant of the hypergraph. Then, we establish a feasible optimization algorithm to compute the Fiedler vector according to the normalized Laplacian tensor. The convergence of the proposed algorithm and the probability of obtaining the Fiedler vector of the hypergraph are analyzed theoretically. Finally, preliminary numerical experiments illustrate that the new a...