Research Activities >
Programs >
Nonlinear Dynamics of Networks
|
Nonlinear Dynamics of Networks
CSIC Building (#406),
Seminar Room 4122.
Directions: home.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 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. |
|