2023/02/07 by Lars Eldén, Eldén, Lars
Computer Science · Engineering · Mathematics · #05C50 #65F30 #68R10 #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2302.03615
openalex publication_date 2023/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of multiway partitioning of an undirected graph is considered. A spectral method is used, where the k > 2 largest eigenvalues of the normalized adjacency matrix (equivalently, the k smallest eigenvalues of the normalized graph Laplacian) are computed. It is shown that the information necessary for partitioning is contained in the subspace spanned by the k eigenvectors. The partitioning is encoded in a matrix Ψ in indicator form, which is computed by approximating the eigenvector matrix by a product of Ψ and an orthogonal matrix. A measure of the distance of a graph to being k-partitionable is defined, as well as two cut (cost) functions, for which Cheeger inequalities are proved; thus the relation between the eigenvalue and partitioning problems is established. Numerical examples are given that demonstrate that the partitioning algorithm is efficient and robust.