Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Partial Recovery Bounds for the Sparse Stochastic Block Model
 
conference paper

Partial Recovery Bounds for the Sparse Stochastic Block Model

Scarlett, Jonathan  
•
Cevher, Volkan  orcid-logo
2016
2016 Ieee International Symposium On Information Theory
International Symposium on Information Theory (ISIT)

In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities $\frac{a}{n}$ and $\frac{b}{n}$ respectively. We consider the sparse setting, in which $a$ and $b$ do not scale with $n$, and provide upper and lower bounds on the proportion of community labels recovered on average. We provide a numerical example for which the bounds are near-matching for moderate values of $a - b$, and matching in the limit as $a-b$ grows large.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

PartialSBM_ISIT_1.pdf

Type

Publisher's Version

Version

Published version

Access type

openaccess

Size

359.01 KB

Format

Adobe PDF

Checksum (MD5)

e966a9ada0515b298dcdd5ec9d928200

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés