First-principles multiway spectral partitioning of graphs

DOI10.1093/COMNET/CNT021MaRDI QIDQ4689342zbMATH OpenOpenAlexFDO

Authors Maria A. Riolo, M. E. J. Newman

Publication date 16 October 2018

Published in Journal of Complex Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.5969

zbMATH Keywords

graph partitioninggraph spectranetworksspectral algorithms

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We consider the minimum-cut partitioning of a graph into more than two parts using spectral methods. While there exist well-established spectral algorithms for this problem that give good results, they have traditionally not been well motivated. Rather than being derived from first principles by minimizing graph cuts, they are typically presented without direct derivation and then proved after the fact to work. In this paper, we take a contrasting approach in which we start with a matrix formulation of the minimum cut problem and then show, via a relaxed optimization, how it can be mapped onto a spectral embedding defined by the leading eigenvectors of the graph Laplacian. The end result is an algorithm that is similar in spirit to, but different in detail from, previous spectral partitioning approaches. In tests of the algorithm we find that it outperforms previous approaches on certain particularly difficult partitioning problems.

Recommendations

• Spectral partitioning with multiple eigenvectors
• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• scientific article; zbMATH DE number 736319

Cited in

(12)

• Underestimated cost of targeted attacks on complex networks
• An algorithm J-SC of detecting communities in complex networks
• Spectral clustering methods for multiplex networks
• Partitions of networks that are robust to vertex permutation dynamics
• Bipartition of graphs based on the normalized cut and spectral methods. I: Minimum normalized cut
• Signed graph partitioning by spectral rounding
• Multi-level spectral graph partitioning method
• Community detection in networks via nonlinear modularity eigenvectors
• A spectral method to detect community structure based on distance modularity matrix
• Optimization via low-rank approximation for community detection in networks
• Multiway Spectral Graph Partitioning: Cut Functions, Cheeger Inequalities, and a Simple Algorithm
• Community detection in complex networks: from statistical foundations to data science applications

This page was built for publication: First-principles multiway spectral partitioning of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4689342)