14
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: not found
      • Article: not found

      Graph Spectra and the Detectability of Community Structure in Networks

      ,

      Physical Review Letters

      American Physical Society (APS)

      Read this article at

      ScienceOpenPublisherPubMed
      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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.

          Related collections

          Most cited references 7

          • Record: found
          • Abstract: not found
          • Article: not found

          Spherical Model of a Spin-Glass

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Algorithms for graph partitioning on the planted partition model

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices

                Bookmark

                Author and article information

                Journal
                PRLTAO
                Physical Review Letters
                Phys. Rev. Lett.
                American Physical Society (APS)
                0031-9007
                1079-7114
                May 2012
                May 1 2012
                : 108
                : 18
                Article
                10.1103/PhysRevLett.108.188701
                22681123
                © 2012

                Comments

                Comment on this article