Spectral Algorithms for Community Detection

Abstract:

    Community detection consists in identification of groups of
    similar items within a population. In the context of online social
    networks, it is a useful primitive for recommending either
    contacts or news items to users. We will consider a particular
    generative probabilistic model for the observations, namely the
    so-called stochastic block model, and generalizations thereof. We
    will describe spectral transformations and associated clustering
    schemes for partitioning objects into distinct groups. Exploiting
    results on the spectrum of random graphs, we will establish
    consistency of these approaches under suitable assumptions, namely
    presence of a sufficiently strong signal in the observed data.