Spectral partitioning with blends of eigenvectors

DOI10.1093/COMNET/CNW033MaRDI QIDQ4985066zbMATH OpenOpenAlexFDO

Authors James P. Fairbanks, David A. Bader, Geoffrey Sanders

Publication date 22 April 2021

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

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

zbMATH Keywords

approximation algorithmscommunity detectiondata analysisdata miningeigenfunctionseigenvaluesgraph partitioningiterative methodsLaplace equationspartitioning 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) Data structures (68P05) Approximation algorithms (68W25)

Abstract: Many common methods for data analysis rely on linear algebra. We provide new results connecting data analysis error to numerical accuracy, which leads to the first meaningful stopping criterion for two way spectral partitioning. More generally, we provide pointwise convergence guarantees so that blends (linear combinations) of eigenvectors can be employed to solve data analysis problems with confidence in their accuracy. We demonstrate this theory on an accessible model problem, the Ring of Cliques, by deriving the relevant eigenpairs and comparing the predicted results to numerical solutions. These results bridge the gap between linear algebra based data analysis methods and the convergence theory of iterative approximation methods.

Recommendations

• Spectral partitioning with multiple eigenvectors
• Spectral Clustering by Recursive Partitioning
• Spectral clustering with eigenvector selection
• Algorithms and Computation
• Spectral clustering
• scientific article; zbMATH DE number 2127748
• 10.1162/jmlr.2003.4.7-8.1261
• scientific article; zbMATH DE number 2062634

Cited in

(3)

• Spectral partitioning with multiple eigenvectors
• A new lower bound on the size of the smallest vertex separator of a graph
• \(\mathrm{Var(1)}\) long memory from bottlenecks and long cycles in network dynamics

This page was built for publication: Spectral partitioning with blends of eigenvectors

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