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

      Graph spectra and the detectability of community structure in networks.

      Physical review letters

      Read this article at

      ScienceOpenPubMed
          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 references7

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

          Benchmark graphs for testing community detection algorithms

            Bookmark
            • 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

                Author and article information

                Journal
                22681123

                Comments

                Comment on this article