Tree-based coarsening and partitioning of complex networks

DOI10.1145/2851496MaRDI QIDQ5266614zbMATH OpenOpenAlexFDO

Authors Roland Glantz, Henning Meyerhenke, Christian Schulz

Publication date 16 June 2017

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2851496

zbMATH Keywords

complex networksconductancefundamental cutsgraph coarseningmultilevel graph partitioningspanning trees

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• \(n\)-level graph partitioning
• Quality matching and local improvement for multilevel graph-partitioning
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• Complex network partitioning using label propagation
• High-quality hierarchical process mapping

Cites work

• \(n\)-level graph partitioning
• A combined evolutionary search and multilevel optimisation approach to graph-partitioning
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A general framework for graph sparsification
• Advanced coarsening schemes for graph partitioning
• Algebraic distance on graphs
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Depth-First Search and Linear Graph Algorithms
• Efficient graph-based image segmentation
• Engineering Algorithms for Approximate Weighted Matching
• Fast computation of small cuts via cycle space sampling
• Graph coarsening and clustering on the GPU
• Graph partitioning
• Graph partitioning models for parallel computing
• Graphs, networks and algorithms. Based on the translation of the 3rd German edition by Tilla Schade in collaboration with the author
• scientific article; zbMATH DE number 1163411 (Why is no real title available?)
• scientific article; zbMATH DE number 1945215 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 5485569 (Why is no real title available?)
• Networks. An introduction.
• On clusterings: good, bad and spectral
• Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Tree-based coarsening and partitioning of complex networks

Cited in

(3)

• A coarse graining algorithm based on \(m\)-order degree in complex network
• Tree-based coarsening and partitioning of complex networks
• Multilevel iterated tabu search for the multi-constraint graph partitioning problem

Describes a project that uses

Uses Software

• SNAP

This page was built for publication: Tree-based coarsening and partitioning of complex networks

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