License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.3
URN: urn:nbn:de:0030-drops-89389
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8938/
Go to the corresponding LIPIcs Volume Portal

Biedermann, Sonja ; Henzinger, Monika ; Schulz, Christian ; Schuster, Bernhard

Memetic Graph Clustering

pdf-format:
LIPIcs-SEA-2018-3.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{biedermann_et_al:LIPIcs:2018:8938,
  author =	{Sonja Biedermann and Monika Henzinger and Christian Schulz and Bernhard Schuster},
  title =	{{Memetic Graph Clustering}},
  booktitle =	{17th International Symposium on Experimental Algorithms  (SEA 2018)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8938},
  URN =		{urn:nbn:de:0030-drops-89389},
  doi =		{10.4230/LIPIcs.SEA.2018.3},
  annote =	{Keywords: Graph Clustering, Evolutionary Algorithms}
}

Keywords: Graph Clustering, Evolutionary Algorithms
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI