Research Activities > Programs > Nonlinear Dynamics of Networks

Nonlinear Dynamics of Networks

CSIC Building (#406), Seminar Room 4122.

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 high-modularity solutions. Time allowing, using a real-world 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 high-modularity partitions and why different heuristics often disagree on the modular composition the same network. I'll conclude with some forward-looking thoughts about the general problem of identifying network modules from connectivity data alone, and the likelihood of circumventing this degeneracy problem.

University of Maryland    

UM Home | Directories | Calendar
Maintained by CSCAMM
Direct questions and comments to

CSCAMM is part of the
College of Computer, Mathematical & Natural Sciences (CMNS)