Skip to content

degeneracy problems for community detection

January 3, 2010

The degenerate modularity landscape for the TPA metabolic networkIn 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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: