A novel spectral algorithm for the identification of overlapping communities

Speaker : Emilie Kaufmann
Date: 10/06/2015
Time: 2:00 pm - 2:30 pm
Location: LINCS Meeting Room 40


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.