1 Search Results for "Matsui, Tomomi"

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.43

Additive Approximation Algorithms for Modularity Maximization

Authors: Yasushi Kawase, Tomomi Matsui, and Atsushi Miyauchi

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

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.

Cite as

Yasushi Kawase, Tomomi Matsui, and Atsushi Miyauchi. Additive Approximation Algorithms for Modularity Maximization. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ISAAC.2016.43,
  author =	{Kawase, Yasushi and Matsui, Tomomi and Miyauchi, Atsushi},
  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 =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.43},
  URN =		{urn:nbn:de:0030-drops-68136},
  doi =		{10.4230/LIPIcs.ISAAC.2016.43},
  annote =	{Keywords: networks, community detection, modularity maximization, approxima- tion algorithms}
}

Refine by Author
1 Kawase, Yasushi
1 Matsui, Tomomi
1 Miyauchi, Atsushi

Refine by Classification

Refine by Keyword
1 approxima- tion algorithms
1 community detection
1 modularity maximization
1 networks

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Matsui, Tomomi"

Additive Approximation Algorithms for Modularity Maximization

Abstract

Cite as

Thanks for your feedback!

Could not send message