Faculty of Computer Science
6050 University Avenue
Dalhousie University
Halifax, NS
MoMiNIS-MITACS SEMINAR
Speaker: Aaron Clauset
Santa Fe Institute
Title: The trouble with community detection in complex networks Data
Date: Tuesday March 30, 2010
Time: 2:30 p.m.
Location: Jacob Slonim Conference Room (430)
6050 University Ave., Halifax
Note: Coffee and cookies will be provided, courtesy of Faculty of Computer Science.
Abstract:
Although widely used in practice, the performance of the popular network clustering technique called "modularity maximization" is not well understood when applied to networks with unknown modular structure. In this talk, I'll show that precisely in the case we want it to perform the best---that is, on modular networks---the modularity function Q exhibits extreme degeneracies, in which the global maximum is hidden among an exponential number of high-modularity solutions. Further, these degenerate solutions can be structurally very dissimilar, suggesting that any particular high-modularity partition, or statistical summary of its structure, should not be taken as representative of the other degenerate solutions. These results partly explain why so many heuristics do well at finding high-modularity partitions and why different heuristics can 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.
Short Biography:
Dr. Aaron Clauset is an Omidyar Fellow at the Santa Fe Institute.His research currently focuses on three distinct areas: the large-scale organizational patterns of complex social, biological and technological networks; the mechanisms that shape the macroevolution of living things (right now, mainly mammals) across large spatial and temporal scales; and the mathematical structure of violent human conflicts, such as modern terrorism and warfare. In all of this work, he uses tools from computer science, physics and statistics to analyze data, characterize its structural patterns, and build computational or mathematical models to explain their origin. He is particularly interested in the interactions between theory and data, and spends a lot of time thinking about tools for characterizing data from complex systems and testing hypotheses.
Speaker URL: http://tuvalu.santafe.edu/~aaronc/
Host contact: Jeannette Janssen janssen@mathstat.dal.ca
