Additive approximation algorithms for modularity maximization

DOI10.1016/J.JCSS.2020.11.005MaRDI QIDQ2221809zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmscommunity detectionmodularity maximizationnetworks

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)

Recommendations

• Additive approximation algorithms for modularity maximization
• Modularity-maximizing graph communities via mathematical programming
• On Finding Graph Clusterings with Maximum Modularity
• Toward optimal community detection: from trees to general weighted networks
• A cutting plane algorithm for modularity maximization problem

Cites work

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

Cited in

(4)

• A locally optimal hierarchical divisive heuristic for bipartite modularity maximization
• Improving heuristics for network modularity maximization using an exact algorithm
• Additive approximation algorithms for modularity maximization
• A study on modularity density maximization: column generation acceleration and computational complexity analysis

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2221809)