Title: Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection,
Abstract: Modularity maximization using greedy algorithms continues to be a popular
approach toward community detection in graphs, even after various better
forming algorithms have been proposed. Apart from its clear mechanism and ease
of implementation, this approach is persistently popular because, presumably,
its risk of algorithmic failure is not well understood. This Rapid
Communication provides insight into this issue by estimating the algorithmic
performance limit of modularity maximization. This is achieved by counting the
number of metastable states under a local update rule. Our results offer a
quantitative insight into the level of sparsity at which a greedy algorithm
typically fails.