%0 Generic
%1 Brandes2006
%A Brandes, U.
%A Delling, D.
%A Gaertler, M.
%A Goerke, R.
%A Hoefer, M.
%A Nikoloski, Z.
%A Wagner, D.
%D 2006
%K community complexity detection modularity network npc
%T Maximizing Modularity is hard
%U http://arxiv.org/abs/physics/0608255
%X Several algorithms have been proposed to compute partitions of networks
into communities that score high on a graph clustering index called
modularity. While publications on these algorithms typically contain
experimental evaluations to emphasize the plausibility of results,
none of these algorithms has been shown to actually compute optimal
partitions. We here settle the unknown complexity status of modularity
maximization by showing that the corresponding decision version is
NP-complete in the strong sense. As a consequence, any efficient,
i.e. polynomial-time, algorithm is only heuristic and yields suboptimal
partitions on many instances.