  Community detection is a fundamental problem in computational sciences with
extensive applications in various fields. The most commonly used methods are
the algorithms designed to maximize modularity over different partitions of the
network nodes. Using 80 real and random networks from a wide range of contexts,
we investigate the extent to which current heuristic modularity maximization
algorithms succeed in returning maximum-modularity (optimal) partitions. We
evaluate (1) the ratio of the algorithms' output modularity to the maximum
modularity for each input graph, and (2) the maximum similarity between their
output partition and any optimal partition of that graph. We compare eight
existing heuristic algorithms against an exact integer programming method that
globally maximizes modularity. The average modularity-based heuristic algorithm
returns optimal partitions for only 19.4% of the 80 graphs considered.
Additionally, results on adjusted mutual information reveal substantial
dissimilarity between the sub-optimal partitions and any optimal partition of
the networks in our experiments. More importantly, our results show that
near-optimal partitions are often disproportionately dissimilar to any optimal
partition. Taken together, our analysis points to a crucial limitation of
commonly used modularity-based heuristics for discovering communities: they
rarely produce an optimal partition or a partition resembling an optimal
partition. If modularity is to be used for detecting communities, exact or
approximate optimization algorithms are recommendable for a more
methodologically sound usage of modularity within its applicability limits.
