Kawase, Yasushi ;
Matsui, Tomomi ;
Miyauchi, Atsushi
Additive Approximation Algorithms for Modularity Maximization
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 polynomialtime (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 nearlyoptimal solution for any instance with a high modularity value. Moreover, we propose a polynomialtime 0.16598additive approximation algorithm for the maximum modularity cut problem. It should be noted that this is the first nontrivial 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:143:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6813},
URN = {urn:nbn:de:0030drops68136},
doi = {10.4230/LIPIcs.ISAAC.2016.43},
annote = {Keywords: networks, community detection, modularity maximization, approxima tion algorithms}
}
07.12.2016
Keywords: 

networks, community detection, modularity maximization, approxima tion algorithms 
Seminar: 

27th International Symposium on Algorithms and Computation (ISAAC 2016)

Issue date: 

2016 
Date of publication: 

07.12.2016 