A novel spectral algorithm for the identification of overlapping communities

When

10/06/2015    
2:00 pm-2:30 pm
Emilie Kaufmann
INRIA

Where

LINCS Meeting Room 40
23, avenue d'Italie, Paris, 75013

Event Type

Spectral algorithms are popular methods for finding a partition of a network into groups of nodes that are densely connected, called communities. However, the structure of many real world networks is better explained by a set of overlapping communities than by a partition. In this talk, I will present combinatorial spectral clustering (CSC), a simple spectral algorithm designed to identify overlapping communities. The algorithm is motivated by a random graph model called stochastic blockmodel with overlap (SBMO), under which it is proved to be consistent. Joint work with Thomas Bonald and Marc Lelarge.