DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2018.3

Memetic Graph Clustering

Authors: Sonja Biedermann, Monika Henzinger, Christian Schulz, and Bernhard Schuster

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

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.

Cite as

Sonja Biedermann, Monika Henzinger, Christian Schulz, and Bernhard Schuster. Memetic Graph Clustering. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{biedermann_et_al:LIPIcs.SEA.2018.3,
  author =	{Biedermann, Sonja and Henzinger, Monika and Schulz, Christian and Schuster, Bernhard},
  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 =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.3},
  URN =		{urn:nbn:de:0030-drops-89389},
  doi =		{10.4230/LIPIcs.SEA.2018.3},
  annote =	{Keywords: Graph Clustering, Evolutionary Algorithms}
}

Search Results

Documents authored by Biedermann, Sonja

Memetic Graph Clustering

Abstract

Cite as

Thanks for your feedback!

Could not send message