Seminar Details
2012-03-20 (14.00) : Limits of Community Detection
At Euler building
Organized by Mathematical Engineering
Speaker :
Vincent TRAAG (UCL)
Abstract :
Many networks can be decomposed into several relatively dense subgraphs, that
are only sparsely connected in between. One of the more popular methods is that
of modularity, which compares the given network to a random null-model. Several
null-models have been suggested, but they all suffer from a similar drawback:
what communities will be found depends on the size of the network. This problem
is known as the resolution-limit. However, it is not well understood what it
entails exactly. We will provide a definition of so called
"resolution-limit-free" methods that captures this notion more rigorously. Using
this definition, we can show that only few sensible methods exist that exhibit
this property. For one of these resolution-limit-free methods, we will provide
an efficient algorithm, and show it performs quite well in various benchmarks.