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.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: