Partitioning (hierarchically clustered) complex networks via size-constrained graph clustering

Henning Meyerhenke (), Peter Sanders () and Christian Schulz ()
Additional contact information
Henning Meyerhenke: Karlsruhe Institute of Technology (KIT), Institute of Theoretical Informatics
Peter Sanders: Karlsruhe Institute of Technology (KIT), Institute of Theoretical Informatics
Christian Schulz: Karlsruhe Institute of Technology (KIT), Institute of Theoretical Informatics

Journal of Heuristics, 2016, vol. 22, issue 5, No 5, 759-782

Abstract: Abstract The most commonly used method to tackle the graph partitioning problem in practice is the multilevel metaheuristic. In this paper we introduce size-constrained label propagation (SCLaP) and show how it can be used to instantiate both the coarsening phase and the refinement phase of multilevel graph partitioning. We mainly target networks with highly irregular and hierarchically clustered structure (but other network types can be partitioned as well). Additionally, we augment the basic algorithm with several extensions to further improve its speed and/or solution quality. Depending on the configuration of the resulting partitioner using SCLaP, we are able to compute high-quality partitions outperforming all competitors, or instead, to compute similarly good partitions as the best competitor in terms of quality, hMetis, while being an order of magnitude faster. Our fastest configuration partitions the largest real-world graph in our study (it has 3.3 billion edges) with sequential code in about ten minutes while cutting less than half of the edges than the fastest competitor, kMetis.

Keywords: Multilevel graph partitioning; Size-constrained graph clustering; Heuristics; Label propagation; Aggressive graph coarsening (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-016-9315-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:22:y:2016:i:5:d:10.1007_s10732-016-9315-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-016-9315-8

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().