For Publishers
DiscoveryMetadataPeer reviewHostingPublishing
For Researchers
JoinPublishReviewCollect
Register
Blog
About
Search
Advanced search
My ScienceOpen
Search
For Publishers
For Researchers
Blog
About
30
views
12
references
 Top references
cited by
0
    
0 reviews
 Review
0
comments
 Comment
0
recommends
+1 Recommend
0 collections
    0
    shares
      48
      similar
       All similar
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Community Detection in Random Networks

      Preprint
      Author(s): ,
      Publication date Created:

      Read this article at

      ScienceOpenArXiv
      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 formalize the problem of detecting a community in a network into testing whether in a given (random) graph there is a subgraph that is unusually dense. We observe an undirected and unweighted graph on N nodes. Under the null hypothesis, the graph is a realization of an Erd\"os-R\'enyi graph with probability p0. Under the (composite) alternative, there is a subgraph of n nodes where the probability of connection is p1 > p0. We derive a detection lower bound for detecting such a subgraph in terms of N, n, p0, p1 and exhibit a test that achieves that lower bound. We do this both when p0 is known and unknown. We also consider the problem of testing in polynomial-time. As an aside, we consider the problem of detecting a clique, which is intimately related to the planted clique problem. Our focus in this paper is in the quasi-normal regime where n p0 is either bounded away from zero, or tends to zero slowly.

          Related collections

          Most cited references12

          • 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.
          Article 0 comments Cited 1190 times – based on 0 reviews
          Preprint
               Review now
            Bookmark
            • Record: found
            • Abstract: found
            • Article: found
            Is Open Access

            Community structure in social and biological networks

            Michelle Girvan, M. Newman (2001)
            A number of recent studies have focused on the statistical properties of networked systems such as social networks and the World-Wide Web. Researchers have concentrated particularly on a few properties which seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this paper, we highlight another property which is found in many networks, the property of community structure, in which network nodes are joined together in tightly-knit groups between which there are only looser connections. We propose a new method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer generated and real-world graphs whose community structure is already known, and find that it detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well-known - a collaboration network and a food web - and find that it detects significant and informative community divisions in both cases.
            Article 0 comments Cited 1183 times – based on 0 reviews
            Preprint
                 Review now
              Bookmark
              • Record: found
              • Abstract: found
              • Article: not found
              Is Open Access

              Community detection in graphs

              Santo Fortunato (2009)
              The modern science of networks has brought significant advances to our understanding of complex systems. One of the most relevant features of graphs representing real systems is community structure, or clustering, i. e. the organization of vertices in clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Such clusters, or communities, can be considered as fairly independent compartments of a graph, playing a similar role like, e. g., the tissues or the organs in the human body. Detecting communities is of great importance in sociology, biology and computer science, disciplines where systems are often represented as graphs. This problem is very hard and not yet satisfactorily solved, despite the huge effort of a large interdisciplinary community of scientists working on it over the past few years. We will attempt a thorough exposition of the topic, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists, from the discussion of crucial issues like the significance of clustering and how methods should be tested and compared against each other, to the description of applications to real networks.
              Article 0 comments Cited 1066 times – based on 0 reviews
              Preprint
                   Review now
                Bookmark
                All references

                Author and article information

                Journal
                Publication date Created: 2013-02-28
                Article
                ArXiV ID: 1302.7099
                SO-VID: f0d0bea4-4427-4bd0-abc4-3b9cbc28535c
                License:

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                Categories math.ST stat.ML stat.TH
                Proxy ccsd

                ScienceOpen disciplines: Machine learning,Statistics theory
                Data availability:
                ScienceOpen disciplines: Machine learning, Statistics theory

                Comments

                Comment on this article