Flow-based algorithms for local graph clustering

DOI10.1137/1.9781611973402.94MaRDI QIDQ5384056zbMATH OpenOpenAlexFDO

Authors Lorenzo Orecchia, Zeyuan Allen Zhu

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/1307.2855

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: Given a subset S of vertices of an undirected graph G, the cut-improvement problem asks us to find a subset S that is similar to A but has smaller conductance. A very elegant algorithm for this problem has been given by Andersen and Lang [AL08] and requires solving a small number of single-commodity maximum flow computations over the whole graph G. In this paper, we introduce LocalImprove, the first cut-improvement algorithm that is local, i.e. that runs in time dependent on the size of the input set A rather than on the size of the entire graph. Moreover, LocalImprove achieves this local behaviour while essentially matching the same theoretical guarantee as the global algorithm of Andersen and Lang. The main application of LocalImprove is to the design of better local-graph-partitioning algorithms. All previously known local algorithms for graph partitioning are random-walk based and can only guarantee an output conductance of O(sqrt{OPT}) when the target set has conductance OPT in [0,1]. Very recently, Zhu, Lattanzi and Mirrokni [ZLM13] improved this to O(OPT / sqrt{CONN}) where the internal connectivity parameter CONN in [0,1] is defined as the reciprocal of the mixing time of the random walk over the graph induced by the target set. In this work, we show how to use LocalImprove to obtain a constant approximation O(OPT) as long as CONN/OPT = Omega(1). This yields the first flow-based algorithm. Moreover, its performance strictly outperforms the ones based on random walks and surprisingly matches that of the best known global algorithm, which is SDP-based, in this parameter regime [MMV12]. Finally, our results show that spectral methods are not the only viable approach to the construction of local graph partitioning algorithm and open door to the study of algorithms with even better approximation and locality guarantees.

Recommendations

• Finding sparse cuts locally using evolving sets
• Almost optimal local graph clustering using evolving sets
• A local graph partitioning algorithm using heat kernel pagerank
• Local flow partitioning for faster edge connectivity
• Using PageRank to Locally Partition a Graph

Cited in

(16)

• Spectral concentration and greedy k-clustering
• Variational perspective on local graph clustering
• Local algorithms for sparse spanning graphs
• Local network community detection with continuous optimization of conductance and weighted kernel k-means
• A Local Clustering Algorithm for Connection Graphs
• An algorithm for improving graph partitions
• Compressive sensing for cut improvement and local clustering
• Hypergraph Cuts with General Splitting Functions
• Statistical guarantees for local graph clustering
• Finding sparse cuts locally using evolving sets
• Local flow partitioning for faster edge connectivity
• Local computation algorithms for graphs of non-constant degrees
• Integer Programming and Combinatorial Optimization
• Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Iterated multilevel simulated annealing for large-scale graph conductance minimization
• Testing cluster structure of graphs

This page was built for publication: Flow-based algorithms for local graph clustering

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