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.ISAAC.2016.43
URN: urn:nbn:de:0030-drops-68136
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6813/
Go to the corresponding LIPIcs Volume Portal

Kawase, Yasushi ; Matsui, Tomomi ; Miyauchi, Atsushi

Additive Approximation Algorithms for Modularity Maximization

pdf-format:
LIPIcs-ISAAC-2016-43.pdf (1 MB)

Abstract

The modularity is a quality function in community detection, which was introduced by Newman and Girvan [Phys. Rev. E, 2004]. Community detection in graphs is now often conducted through modularity maximization: given an undirected graph G = (V, E), we are asked to find a partition C of V that maximizes the modularity. Although numerous algorithms have been developed to date, most of them have no theoretical approximation guarantee. Recently, to overcome this issue, the design of modularity maximization algorithms with provable approximation guarantees has attracted significant attention in the computer science community.

In this study, we further investigate the approximability of modularity maximization. More specifically, we propose a polynomial-time (cos(frac{3 - sqrt{5}}{4} pi) - frac{1 - sqrt{5}}{8})-additive approximation algorithm for the modularity maximization problem. Note here that cos(frac{3 - sqrt{5}}{4} pi) - frac{1 - sqrt{5}}{8} < 0.42084 holds. This improves the current best additive approximation error of 0.4672, which was recently provided by Dinh, Li, and Thai (2015). Interestingly, our analysis also demonstrates that the proposed algorithm obtains a nearly-optimal solution for any instance with a high modularity value. Moreover, we propose a polynomial-time 0.16598-additive approximation algorithm for the maximum modularity cut problem. It should be noted that this is the first non-trivial approximability result for the problem. Finally, we demonstrate that our approximation algorithm can be extended to some related problems.

BibTeX - Entry

@InProceedings{kawase_et_al:LIPIcs:2016:6813,
  author =	{Yasushi Kawase and Tomomi Matsui and Atsushi Miyauchi},
  title =	{{Additive Approximation Algorithms for Modularity Maximization}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{43:1--43:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6813},
  URN =		{urn:nbn:de:0030-drops-68136},
  doi =		{10.4230/LIPIcs.ISAAC.2016.43},
  annote =	{Keywords: networks, community detection, modularity maximization, approxima- tion algorithms}
}

Keywords: networks, community detection, modularity maximization, approxima- tion algorithms
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

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