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

      Clique Percolation in Random 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

          The notion of k-clique percolation in random graphs is introduced, where k is the size of the complete subgraphs whose large scale organizations are analytically and numerically investigated. For the Erdos-Rényi graph of N vertices we obtain that the percolation transition of k-cliques takes place when the probability of two vertices being connected by an edge reaches the threshold p(c) (k) = [(k - 1)N](-1/(k - 1)). At the transition point the scaling of the giant component with N is highly nontrivial and depends on k. We discuss why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks.

          Related collections

          Most cited references9

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

          Defining and identifying communities in networks.

          The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic and protein networks), or technological problems (optimization of large infrastructures). Several types of algorithms exist for revealing the community structure in networks, but a general and quantitative definition of community is not implemented in the algorithms, leading to an intrinsic difficulty in the interpretation of the results without any additional nontopological information. In this article we deal with this problem by showing how quantitative definitions of community are implemented in practice in the existing algorithms. In this way the algorithms for the identification of the community structure become fully self-contained. Furthermore, we propose a local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability. The algorithm is tested on artificial and real-world graphs. In particular, we show how the algorithm applies to a network of scientific collaborations, which, for its size, cannot be attacked with the usual methods. This type of local algorithm could open the way to applications to large-scale technological and biological systems.
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Random graphs with arbitrary degree distributions and their applications

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

              Social Network Analysis

              John Scott (1988)
                Bookmark

                Author and article information

                Journal
                PRLTAO
                Physical Review Letters
                Phys. Rev. Lett.
                American Physical Society (APS)
                0031-9007
                1079-7114
                April 2005
                April 29 2005
                : 94
                : 16
                Article
                10.1103/PhysRevLett.94.160202
                15904198
                59002f80-510e-44c7-9bd8-4b72779ace22
                © 2005

                http://link.aps.org/licenses/aps-default-license

                History

                Comments

                Comment on this article