Document Open Access Logo

Additive Approximation Algorithms for Modularity Maximization

Authors Yasushi Kawase, Tomomi Matsui, Atsushi Miyauchi

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.43.pdf
  • Filesize: 1.02 MB
  • 13 pages

Document Identifiers

Author Details

Yasushi Kawase
Tomomi Matsui
Atsushi Miyauchi

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ISAAC.2016.43

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.

Subject Classification

Keywords
  • networks
  • community detection
  • modularity maximization
  • approxima- tion algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. G. Agarwal and D. Kempe. Modularity-maximizing graph communities via mathematical programming. Eur. Phys. J. B, 66(3):409-418, 2008. Google Scholar
  2. N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Mach. Learn., 56(1-3):89-113, 2004. Google Scholar
  3. M. J. Barber. Modularity and community detection in bipartite networks. Phys. Rev. E, 76:066102, 2007. Google Scholar
  4. V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks. J. Stat. Mech.: Theory Exp., 2008:P10008, 2008. Google Scholar
  5. U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner. On modularity clustering. IEEE Trans. Knowl. Data Eng., 20(2):172-188, 2008. Google Scholar
  6. S. Cafieri, A. Costa, and P. Hansen. Reformulation of a model for hierarchical divisive graph modularity maximization. Ann. Oper. Res., 222(1):213-226, 2014. Google Scholar
  7. M. Charikar, V. Guruswami, and A. Wirth. Clustering with qualitative information. J. Comput. Syst. Sci., 71(3):360-383, 2005. Google Scholar
  8. B. DasGupta and D. Desai. On the complexity of Newman’s community finding approach for biological and social networks. J. Comput. Syst. Sci., 79(1):50-67, 2013. Google Scholar
  9. T. N. Dinh, X. Li, and M. T. Thai. Network clustering via maximizing modularity: Approximation algorithms and theoretical limits. In ICDM'15, pages 101-110, 2015. Google Scholar
  10. T. N. Dinh and M. T. Thai. Community detection in scale-free networks: Approximation algorithms for maximizing modularity. IEEE J. Sel. Areas Commun., 31(6):997-1006, 2013. Google Scholar
  11. S. Fortunato. Community detection in graphs. Phys. Rep., 486(3):75-174, 2010. Google Scholar
  12. S. Fortunato and M. Barthélemy. Resolution limit in community detection. Proc. Natl. Acad. Sci. U.S.A., 104(1):36-41, 2007. Google Scholar
  13. A. Frieze and R. Kannan. The regularity lemma and approximation schemes for dense problems. In FOCS'96, pages 12-20, 1996. Google Scholar
  14. D. Gibson, R. Kumar, and A. Tomkins. Discovering large dense subgraphs in massive graphs. In VLDB'05, pages 721-732, 2005. Google Scholar
  15. M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115-1145, 1995. Google Scholar
  16. M. Grötschel and Y. Wakabayashi. A cutting plane algorithm for a clustering problem. Math. Program., 45(1-3):59-96, 1989. Google Scholar
  17. R. Guimerà and L. A. N. Amaral. Functional cartography of complex metabolic networks. Nature, 433(7028):895-900, 2005. Google Scholar
  18. Yasushi Kawase, Tomomi Matsui, and Atsushi Miyauchi. Additive approximation algorithms for modularity maximization. arXiv:1601.03316, 2016. Google Scholar
  19. E. A. Leicht and M. E. J. Newman. Community structure in directed networks. Phys. Rev. Lett., 100:118703, 2008. Google Scholar
  20. A. Miyauchi and Y. Miyamoto. Computing an upper bound of modularity. Eur. Phys. J. B, 86:302, 2013. Google Scholar
  21. A. Miyauchi and N. Sukegawa. Maximizing Barber’s bipartite modularity is also hard. Optim. Lett., 9(5):897-913, 2015. Google Scholar
  22. M. E. J. Newman. Analysis of weighted networks. Phys. Rev. E, 70:056131, 2004. Google Scholar
  23. M. E. J. Newman. Modularity and community structure in networks. Proc. Natl. Acad. Sci. U.S.A., 103(23):8577-8582, 2006. Google Scholar
  24. M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E, 69:026113, 2004. Google Scholar
  25. L. Waltman and N. J. van Eck. A smart local moving algorithm for large-scale modularity-based community detection. Eur. Phys. J. B, 86(11):1-14, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact