24
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Deciphering Network Community Structure by Surprise

      research-article
      , *
      PLoS ONE
      Public Library of Science

      Read this article at

      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

          The analysis of complex networks permeates all sciences, from biology to sociology. A fundamental, unsolved problem is how to characterize the community structure of a network. Here, using both standard and novel benchmarks, we show that maximization of a simple global parameter, which we call Surprise ( S), leads to a very efficient characterization of the community structure of complex synthetic networks. Particularly, S qualitatively outperforms the most commonly used criterion to define communities, Newman and Girvan's modularity (Q). Applying S maximization to real networks often provides natural, well-supported partitions, but also sometimes counterintuitive solutions that expose the limitations of our previous knowledge. These results indicate that it is possible to define an effective global criterion for community structure and open new routes for the understanding of complex networks.

          Related collections

          Most cited references25

          • Record: found
          • Abstract: found
          • Article: found
          Is Open Access

          Modularity and community structure in networks

          M. Newman (2006)
          Many networks of interest in the sciences, including a variety of social and biological networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure has attracted considerable recent attention. One of the most sensitive detection methods is optimization of the quality function known as "modularity" over the possible divisions of a network, but direct application of this method using, for instance, simulated annealing is computationally costly. Here we show that the modularity can be reformulated in terms of the eigenvectors of a new characteristic matrix for the network, which we call the modularity matrix, and that this reformulation leads to a spectral algorithm for community detection that returns results of better quality than competing methods in noticeably shorter running times. We demonstrate the algorithm with applications to several network data sets.
            Bookmark
            • Record: found
            • Abstract: found
            • Article: found
            Is Open Access

            Maps of random walks on complex networks reveal community structure

            To comprehend the multipartite organization of large-scale biological and social systems, we introduce a new information theoretic approach that reveals community structure in weighted and directed networks. The method decomposes a network into modules by optimally compressing a description of information flows on the network. The result is a map that both simplifies and highlights the regularities in the structure and their relationships. We illustrate the method by making a map of scientific communication as captured in the citation patterns of more than 6000 journals. We discover a multicentric organization with fields that vary dramatically in size and degree of integration into the network of science. Along the backbone of the network -- including physics, chemistry, molecular biology, and medicine -- information flows bidirectionally, but the map reveals a directional pattern of citation from the applied fields to the basic sciences.
              Bookmark
              • Record: found
              • Abstract: found
              • Article: found
              Is Open Access

              Resolution limit in community detection

              Detecting community structure is fundamental to clarify the link between structure and function in complex networks and is used for practical applications in many disciplines. A successful method relies on the optimization of a quantity called modularity [Newman and Girvan, Phys. Rev. E 69, 026113 (2004)], which is a quality index of a partition of a network into communities. We find that modularity optimization may fail to identify modules smaller than a scale which depends on the total number L of links of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined. The probability that a module conceals well-defined substructures is the highest if the number of links internal to the module is of the order of \sqrt{2L} or smaller. We discuss the practical consequences of this result by analyzing partitions obtained through modularity optimization in artificial and real networks.
                Bookmark

                Author and article information

                Contributors
                Role: Editor
                Journal
                PLoS One
                plos
                plosone
                PLoS ONE
                Public Library of Science (San Francisco, USA )
                1932-6203
                2011
                1 September 2011
                : 6
                : 9
                : e24195
                Affiliations
                [1]Instituto de Biomedicina de Valencia, Consejo Superior de Investigaciones Científicas, Valencia, Spain
                Tel Aviv University, Israel
                Author notes

                Conceived and designed the experiments: RA IM. Performed the experiments: RA. Analyzed the data: RA. Contributed reagents/materials/analysis tools: RA. Wrote the paper: IM.

                Article
                PONE-D-11-06682
                10.1371/journal.pone.0024195
                3164713
                21909420
                b755f362-d4ca-4bad-938f-643217171fe8
                Aldecoa, Marín. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
                History
                : 14 April 2011
                : 4 August 2011
                Page count
                Pages: 8
                Categories
                Research Article
                Biology
                Computational Biology
                Genomics
                Genome Analysis Tools
                Genetic Networks
                Metabolic Networks
                Regulatory Networks
                Signaling Networks
                Genetics
                Gene Networks
                Genomics
                Genome Analysis Tools
                Genetic Networks
                Neuroscience
                Neural Networks
                Systems Biology
                Theoretical Biology
                Computer Science
                Mathematics
                Applied Mathematics
                Complex Systems
                Social and Behavioral Sciences
                Sociology
                Social Networks

                Uncategorized
                Uncategorized

                Comments

                Comment on this article