DROPS

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.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}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.44

The Densest Subgraph Problem with a Convex/Concave Size Function

Authors: Yasushi Kawase and Atsushi Miyauchi

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

Abstract

Given an edge-weighted undirected graph G = (V, E, w), the density of S subseteq V is defined as w(S)/|S|, where w(S) is the sum of weights of the edges in the subgraph induced by S. The densest subgraph problem asks for S subseteq V that maximizes the density w(S)/|S|. The problem has received significant attention recently because it can be solved exactly in polynomial time. However, the densest subgraph problem has a drawback; it may happen that the obtained subset is too large or too small in comparison with the desired size of the output. In this study, we address the size issue by generalizing the density of S subseteq V. Specifically, we introduce the f -density of S subseteq V, which is defined as w(S)/f (|S|), where f : Z geq 0 to R geq 0 is a monotonically non-decreasing function. In the f-densest subgraph problem (f-DS), we are asked to find S subseteq V that maximizes the f-density w(S)/f (|S|). Although f-DS does not explicitly specify the size of the output subset of vertices, we can handle the above size issue using a convex size function f or a concave size function f appropriately. For f-DS with convex function f, we propose a nearly-linear-time algorithm with a provable approximation guarantee. In particular, for f-DS with f(x) = x^alpha (alpha in [1, 2]), our algorithm has an approximation ratio of 2 · n^{(alpha-1)(2-alpha)}. On the other hand, for f-DS with concave function f , we propose a linear-programming-based polynomial-time exact algorithm. It should be emphasized that this algorithm obtains not only an optimal solution to the problem but also subsets of vertices corresponding to the extreme points of the upper convex hull of {(|S|, w(S)) | S subseteq V }, which we refer to as the dense frontier points. We also propose a flow-based combinatorial exact algorithm for unweighted graphs that runs in O(n^3) time. Finally, we propose a nearly-linear-time 3-approximation algorithm.

Cite as

Yasushi Kawase and Atsushi Miyauchi. The Densest Subgraph Problem with a Convex/Concave Size Function. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 44:1-44:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kawase_et_al:LIPIcs.ISAAC.2016.44,
  author =	{Kawase, Yasushi and Miyauchi, Atsushi},
  title =	{{The Densest Subgraph Problem with a Convex/Concave Size Function}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{44:1--44:12},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.44},
  URN =		{urn:nbn:de:0030-drops-68149},
  doi =		{10.4230/LIPIcs.ISAAC.2016.44},
  annote =	{Keywords: graphs, dense subgraph extraction, densest subgraph problem, approxi- mation algorithms}
}

Search Results

Documents authored by Miyauchi, Atsushi

Additive Approximation Algorithms for Modularity Maximization

Abstract

Cite as

The Densest Subgraph Problem with a Convex/Concave Size Function

Abstract

Cite as

Thanks for your feedback!

Could not send message