(Semi-)External Algorithms for Graph Partitioning and Clustering

DOI10.1137/1.9781611973754.4MaRDI QIDQ5232520zbMATH OpenOpenAlexFDO

Authors Yaroslav Akhremtsev, Peter Sanders, Christian Schulz

Publication date 12 September 2019

Published in 2015 Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: In this paper, we develop semi-external and external memory algorithms for graph partitioning and clustering problems. Graph partitioning and clustering are key tools for processing and analyzing large complex networks. We address both problems in the (semi-)external model by adapting the size-constrained label propagation technique. Our (semi-)external size-constrained label propagation algorithm can be used to compute graph clusterings and is a prerequisite for the (semi-)external graph partitioning algorithm. The algorithm is then used for both the coarsening and the refinement phase of a multilevel algorithm to compute graph partitions. Our algorithm is able to partition and cluster huge complex networks with billions of edges on cheap commodity machines. Experiments demonstrate that the semi-external graph partitioning algorithm is scalable and can compute high quality partitions in time that is comparable to the running time of an efficient internal memory implementation. A parallelization of the algorithm in the semi-external model further reduces running time.

Recommendations

• Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms
• Bootstrap clustering for graph partitioning
• Optimal clustering of multipartite graphs
• Graph partitioning using linear and semidefinite programming
• scientific article; zbMATH DE number 991436
• scientific article; zbMATH DE number 5761786
• Approximate algorithms for graph clustering problem

Cited in

(8)

• Moving clusters within a memetic algorithm for graph partitioning
• Complex network partitioning using label propagation
• External-memory network analysis algorithms for naturally sparse graphs
• Practical minimum cut algorithms
• Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
• Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering
• Graph coarsening and clustering on the GPU
• Buffered Streaming Graph Partitioning

This page was built for publication: (Semi-)External Algorithms for Graph Partitioning and Clustering

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