Additive approximation algorithms for modularity maximization

DOI10.1016/j.jcss.2020.11.005zbMath1477.68538OpenAlexW3113097209MaRDI QIDQ2221809

Yasushi Kawase, Tomomi Matsui, Atsushi Miyauchi

Publication date: 2 February 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6813/

zbMATH Keywords

networksapproximation algorithmscommunity detectionmodularity maximization

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (1)

A study on modularity density maximization: column generation acceleration and computational complexity analysis

Cites Work

• Reformulation of a model for hierarchical divisive graph modularity maximization
• Correlation clustering
• Modularity-maximizing graph communities via mathematical programming
• A cutting plane algorithm for a clustering problem
• On the complexity of Newman's community finding approach for biological and social networks
• Maximizing Barber's bipartite modularity is also hard
• On a connection between small set expansions and modularity clustering
• Clustering with qualitative information
• The Design of Approximation Algorithms
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Additive Approximation Algorithms for Modularity Maximization
• Fast unfolding of communities in large networks
• Quadratic forms on graphs

This page was built for publication: Additive approximation algorithms for modularity maximization