Memetic graph clustering

DOI10.4230/LIPICS.SEA.2018.3MaRDI QIDQ5140709zbMATH OpenOpenAlexFDO

Authors Sonja Biedermann, Christian Schulz, Bernhard Schuster, Monika R. Henzinger

Publication date 16 December 2020

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

zbMATH Keywords

evolutionary algorithmsgraph clustering

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50)

Abstract: It is common knowledge that there is no single best strategy for graph clustering, which justifies a plethora of existing approaches. In this paper, we present a general memetic algorithm, VieClus, to tackle the graph clustering problem. This algorithm can be adapted to optimize different objective functions. A key component of our contribution are natural recombine operators that employ ensemble clusterings as well as multi-level techniques. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high-quality solutions in a short amount of time. We instantiate our scheme with local search for modularity and show that our algorithm successfully improves or reproduces all entries of the 10th DIMACS implementation~challenge under consideration using a small amount of time.

Recommendations

• Moving clusters within a memetic algorithm for graph partitioning
• Graph clustering
• An ensemble learning strategy for graph clustering
• An efficient memetic algorithm for the graph partitioning problem
• A Scalable Multilevel Algorithm for Graph Clustering and Community Structure Detection

Cites work

• An ensemble learning strategy for graph clustering
• Distributed Evolutionary Graph Partitioning
• Engineering graph clustering: models and experimental evaluation
• Fast unfolding of communities in large networks
• Graph clustering
• Graph Clustering and Minimum Cut Trees
• scientific article; zbMATH DE number 1333614 (Why is no real title available?)
• scientific article; zbMATH DE number 976350 (Why is no real title available?)
• scientific article; zbMATH DE number 194544 (Why is no real title available?)
• Network analysis. Methodological foundations.
• On clusterings: good, bad and spectral

Cited in

(3)

• Moving clusters within a memetic algorithm for graph partitioning
• Some properties of E-quality function for network clustering
• An ensemble learning strategy for graph clustering

Describes a project that uses

Uses Software

• KaFFPa
• VNDS
• LPAm+
• KaHIP

This page was built for publication: Memetic graph clustering

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