The parameterised complexity of computing the maximum modularity of a graph

DOI10.1007/S00453-019-00649-7MaRDI QIDQ786031zbMATH OpenOpenAlexWikidataFDO

Authors Kitty Meeks, Fiona Skerman

Publication date 12 August 2020

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-019-00649-7

zbMATH Keywords

community detectionmodularitypathwidthvertex coverinteger quadratic programming

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• scientific article; zbMATH DE number 7378595
• Maximum modular graphs
• On Finding Graph Clusterings with Maximum Modularity
• Modular-width: an auxiliary parameter for parameterized parallel complexity
• Parameterized Algorithms for Modular-Width

Cites work

• scientific article; zbMATH DE number 5725105 (Why is no real title available?)
• A linear time algorithm for finding tree-decompositions of small treewidth
• Additive approximation algorithms for modularity maximization
• Communities in Networks
• Fast unfolding of communities in large networks
• Fundamentals of parameterized complexity
• Modularity in several random graph models
• Modularity of Erdős-Rényi random graphs
• Modularity of Erdős-Rényi random graphs
• Modularity of regular and treelike graphs
• On the complexity of Newman's community finding approach for biological and social networks
• Parameterized algorithms
• Treewidth. Computations and approximations
• What makes equitable connected partition easy

Cited in

(7)

• Grundy Distinguishes Treewidth from Pathwidth
• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• scientific article; zbMATH DE number 1136076 (Why is no real title available?)
• Maximum modular graphs
• Grundy distinguishes treewidth from pathwidth
• The complexity of modular graph automorphism
• scientific article; zbMATH DE number 7378595 (Why is no real title available?)

Describes a project that uses

Uses Software

• GenLouvain

This page was built for publication: The parameterised complexity of computing the maximum modularity of a graph

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