Global and local information in clustering labeled block models
- Submitting institution
-
University of Oxford
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 1975
- Type
- D - Journal article
- DOI
-
10.1109/TIT.2016.2516564
- Title of journal
- IEEE Transactions on Information Theory
- Article number
- -
- First page
- 5906
- Volume
- 62
- Issue
- 10
- ISSN
- 1557-9654
- Open access status
- Out of scope for open access requirements
- Month of publication
- October
- Year of publication
- 2016
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
-
- Citation count
- 9
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This article extends an APPROX-RANDOM�14 paper. The stochastic block model is widely studied as a random graph model exhibiting community structure. This work considers a variant, more relevant to practice, which assumes that label information for a small fraction of the nodes is available. It shows that in this case simple local algorithms can be used to infer the community structure. The work also establishes that recovery in this setting is possible even below the Kesten-Stigum bound when the number of communities grows, exhibiting interesting new behaviour in this model.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
