Back to Search
Start Over
Additive approximation algorithms for modularity maximization.
- Source :
-
Journal of Computer & System Sciences . May2021, Vol. 117, p182-201. 20p. - Publication Year :
- 2021
-
Abstract
- The modularity is the best known and widely used quality function for community detection in graphs. We investigate the approximability of the modularity maximization problem and some related problems. We first design a polynomial-time 0.4209-additive approximation algorithm for the modularity maximization problem, which improves the current best additive approximation error of 0.4672. Our theoretical analysis also demonstrates that the proposed algorithm obtains a nearly-optimal solution for any instance with a high modularity value. We next design a polynomial-time 0.1660-additive approximation algorithm for the maximum modularity cut problem. Finally, we extend our algorithm to some related problems. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 117
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 147930171
- Full Text :
- https://doi.org/10.1016/j.jcss.2020.11.005