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

      Computational Lower Bounds for Community Detection on Random Graphs

      Preprint
      , ,

      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

          This paper studies the problem of detecting the presence of a small dense community planted in a large Erd\H{o}s-R\'enyi random graph \(\mathcal{G}(N,q)\), where the edge probability within the community exceeds \(q\) by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computational complexity of detecting the community exhibits the following phase transition phenomenon: As the graph size \(N\) grows and the graph becomes sparser according to \(q=N^{-\alpha}\), there exists a critical value of \(\alpha = \frac{2}{3}\), below which there exists a computationally intensive procedure that can detect far smaller communities than any computationally efficient procedure, and above which a linear-time procedure is statistically optimal. The results also lead to the average-case hardness results for recovering the dense community and approximating the densest \(K\)-subgraph.

          Related collections

          Author and article information

          Journal
          2014-06-25
          2015-03-11
          Article
          1406.6625
          47f3f09d-0995-49c4-8153-436b8b5fd4d7

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

          History
          Custom metadata
          28 pages
          math.ST cs.CC stat.ML stat.TH

          Theoretical computer science,Machine learning,Statistics theory
          Theoretical computer science, Machine learning, Statistics theory

          Comments

          Comment on this article