degeneracy problems for community detection
In the summer of 2008 I participated in the REU program at the Santa Fe Institute (which I highly recommend to anyone who is interested), and there I started working on the problem of community detection in complex networks, and in particular, the method known popularly known as modularity maximization. This paper is the result of a collaboration with Aaron Clauset (my mentor) and Yves-Alexandre de Montjoye concerning the significance of modularity-based community detection algorithms in practical contexts. Our main finding is a degeneracy problem for networks with highly modular or hierarchical structure, whereby the modularity function admits an exponential number of high-modularity partitions that consist of highly dissimilar community assignments. This runs counter to the conventional understanding in the literature, where a degenerate modularity landscape is usually assumed to be a sign of weak community structure. Furthermore, since modularity maximization is in general an NP-Hard problem, we cannot necessarily trust the results of approximate maximization algorithms, at least when it comes to community assignments. The present version of our paper is available here.