Graph Spectra and the Detectability of Community Structure in Networks

    Phys. Rev. Lett. 108, 188701 – Published 1 May 2012
    Raj Rao Nadakuditi and M. E. J. Newman

    Abstract

    We study networks that display community structure—groups of nodes within which connections are unusually dense. Using methods from random matrix theory, we calculate the spectra of such networks in the limit of large size, and hence demonstrate the presence of a phase transition in matrix methods for community detection, such as the popular modularity maximization method. The transition separates a regime in which such methods successfully detect the community structure from one in which the structure is present but is not detected. By comparing these results with recent analyses of maximum-likelihood methods, we are able to show that spectral modularity maximization is an optimal detection method in the sense that no other method will succeed in the regime where the modularity method fails.

    DOI: http://dx.doi.org/10.1103/PhysRevLett.108.188701

    • Figure
    • Figure
    • Received 14 February 2012
    • Published 1 May 2012

    © 2012 American Physical Society

    CHORUS
    Article part of CHORUS

    Authors & Affiliations

    Raj Rao Nadakuditi1 and M. E. J. Newman2

    • 1Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109, USA
    • 2Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109, USA

    References

    Click to Expand

    Authorization Required


    ×
    ×

    Images

    1 of 2
    ×

    Log In

    Cancel
    ×

    Search


    Article Lookup
    Paste a citation or DOI

    Enter a citation
    ×