Nonlinear Dynamics of Networks
CSIC Building (#406),
Seminar Room 4122.
Directions: www.cscamm.umd.edu/directions

Extreme degeneracies in the module identification problem
Aaron Clauset
Santa Fe Institute

Abstract:
Although widely used in practice, the performance of the popular module identification technique called "modularity maximization" is not well understood in practical contexts. In this talk, I'll show that when applied to networks with modular structure the modularity function Q exhibits extreme degeneracies in which the global maximum is hidden among an exponential number of highmodularity solutions. Time allowing, using a realworld network as an example, I'll show that these degenerate solutions can also be structurally very dissimilar, implying that any particular partition derived from this approach should be treated with caution. Notably, these results explain why so many heuristics perform well in practice at finding highmodularity partitions and why different heuristics often disagree on the modular composition the same network. I'll conclude with some forwardlooking thoughts about the general problem of identifying network modules from connectivity data alone, and the likelihood of circumventing this degeneracy problem. 
