  The modularity is a quality function in community detection, which was
introduced by Newman and Girvan (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 $\mathcal{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
$\left(\cos\left(\frac{3-\sqrt{5}}{4}\pi\right) -
\frac{1+\sqrt{5}}{8}\right)$-additive approximation algorithm for the
modularity maximization problem. Note here that
$\cos\left(\frac{3-\sqrt{5}}{4}\pi\right) - \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 very 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.
