Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/96290
Title: | The Fiedler vector of a Laplacian tensor for hypergraph partitioning | Authors: | Chen, Y Qi, L Zhang, X |
Issue Date: | 2017 | Source: | SIAM journal on scientific computing, 2017, v. 39, no. 6, p. A2508-A2537 | Abstract: | 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 approach based on a hypergraph-based Fiedler vector is effective and promising for some combinatorial optimization problems arising from subspace partitioning and face clustering. | Keywords: | Eigenvalue and eigenvector Face clustering Fiedler vector Hypergraph partitioning Laplacian tensor Optimization |
Publisher: | Society for Industrial and Applied Mathematics | Journal: | SIAM journal on scientific computing | ISSN: | 1064-8275 | EISSN: | 1095-7197 | DOI: | 10.1137/16M1094828 | Rights: | ©2017 Society for Industrial and Applied Mathematics The following publication Chen, Y., Qi, L., & Zhang, X. (2017). The Fiedler vector of a Laplacian tensor for hypergraph partitioning. SIAM Journal on Scientific Computing, 39(6), A2508-A2537 is available at https://doi.org/10.1137/16M1094828 |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
16m1094828.pdf | 1.44 MB | Adobe PDF | View/Open |
Page views
78
Last Week
0
0
Last month
Citations as of Oct 13, 2024
Downloads
120
Citations as of Oct 13, 2024
SCOPUSTM
Citations
30
Citations as of Oct 17, 2024
WEB OF SCIENCETM
Citations
31
Citations as of Oct 17, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.