The Parameterised Complexity of Computing the Maximum Modularity of a Graph
Authors:
Open Access
- 8 November 2019
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 82 (8) , 2174-2199
Abstract
The maximum modularity of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be $$\textsf {NP}$$ -complete in general, and in practice a range of heuristics are used to construct partitions of the vertex-set which give lower bounds on the maximum modularity but without any guarantee on how close these bounds are to the true maximum. In this paper we investigate the parameterised complexity of determining the maximum modularity with respect to various standard structural parameterisations of the input graph G. We show that the problem belongs to $$\textsf {FPT}$$ when parameterised by the size of a minimum vertex cover for G, and is solvable in polynomial time whenever the treewidth or max leaf number of G is bounded by some fixed constant; we also obtain an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation to the maximum modularity. On the other hand we show that the problem is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set.
Keywords
All Related Versions
Funding Information
- Royal Society of Edinburgh
- Ragnar Söderbergs stiftelse
This publication has 18 references indexed in Scilit:
- Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits2015
- On the complexity of Newmanʼs community finding approach for biological and social networksJournal of Computer and System Sciences, 2013
- Communities and bottlenecks: Trees and treelike networks have high modularityPhysical Review E, 2012
- Limits of modularity maximization in community detectionPhysical Review E, 2011
- Community detection in graphsPhysics Reports, 2010
- What Makes Equitable Connected Partition Easy2009
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- On Modularity ClusteringIEEE Transactions on Knowledge and Data Engineering, 2007
- Finding and evaluating community structure in networksPhysical Review E, 2004
- A linear time algorithm for finding tree-decompositions of small treewidth1993