Partitioning into expanders

DOI10.1137/1.9781611973402.93MaRDI QIDQ5384055zbMATH OpenOpenAlexFDO

Authors Shayan Oveis Gharan, Luca Trevisan

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

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) Analysis of algorithms (68W40)

Abstract: Let G=(V,E) be an undirected graph, lambda_k be the k-th smallest eigenvalue of the normalized laplacian matrix of G. There is a basic fact in algebraic graph theory that lambda_k > 0 if and only if G has at most k-1 connected components. We prove a robust version of this fact. If lambda_k>0, then for some 1leq ellleq k-1, V can be {em partitioned} into l sets P_1,ldots,P_l such that each P_i is a low-conductance set in G and induces a high conductance induced subgraph. In particular, phi(P_i)=O(l^3sqrt{lambda_l}) and phi(G[P_i]) >= lambda_k/k^2). We make our results algorithmic by designing a simple polynomial time spectral algorithm to find such partitioning of G with a quadratic loss in the inside conductance of P_i's. Unlike the recent results on higher order Cheeger's inequality [LOT12,LRTV12], our algorithmic results do not use higher order eigenfunctions of G. If there is a sufficiently large gap between lambda_k and lambda_{k+1}, more precisely, if lambda_{k+1} >= poly(k) lambda_{k}^{1/4} then our algorithm finds a k partitioning of V into sets P_1,...,P_k such that the induced subgraph G[P_i] has a significantly larger conductance than the conductance of P_i in G. Such a partitioning may represent the best k clustering of G. Our algorithm is a simple local search that only uses the Spectral Partitioning algorithm as a subroutine. We expect to see further applications of this simple algorithm in clustering applications.

Recommendations

• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• Many sparse cuts via higher eigenvalues
• Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions

Cited in

(20)

• Spectral concentration and greedy k-clustering
• Remarks on partitions into expanders
• Convex programming based spectral clustering
• Distributed detection of clusters of arbitrary size
• Social pressure in opinion dynamics
• Turning the Partition Crank
• Maximum transfer distance between partitions
• Many sparse cuts via higher eigenvalues
• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• Partitioning well-clustered graphs: spectral clustering works!
• scientific article; zbMATH DE number 7651209 (Why is no real title available?)
• Bipartite communities via spectral partitioning
• Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks
• Approximately counting independent sets in bipartite graphs via graph containers
• Efficient algorithms for the Potts model on small-set expanders
• Testing higher-order clusterability on graphs
• A sublinear time tester for max-cut on clusterable graphs
• Nearly optimal local algorithms for constructing sparse spanners of clusterable graphs
• Testing higher-order clusterability on graphs
• Testing cluster structure of graphs

This page was built for publication: Partitioning into expanders

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