Sima, Jin and Zhao, Feng and Huang, Shao-Lun (2021) Exact Recovery in the Balanced Stochastic Block Model with Side Information. In: 2021 IEEE Information Theory Workshop (ITW). IEEE , Piscataway, NJ, pp. 1-6. ISBN 978-1-6654-0312-2. https://resolver.caltech.edu/CaltechAUTHORS:20220105-582974400
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220105-582974400
Abstract
The role that side information plays in improving the exact recovery threshold in the stochastic block model (SBM) has been studied in many aspects. This paper studies exact recovery in n node balanced binary symmetric SBM with side information, given in the form of O(log n) i.i.d. samples at each node. A sharp exact recovery threshold is obtained and turns out to coincide with an existing threshold result, where no balanced constraint is imposed. Our main contribution is an efficient semi-definite programming (SDP) algorithm that achieves the optimal exact recovery threshold. Compared to the existing works on SDP algorithm for SBM with constant number of samples as side information, the challenge in this paper is to deal with the number of samples increasing in n.
| Item Type: | Book Section | ||||||
|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||
| ORCID: |
| ||||||
| Additional Information: | © 2021 IEEE. | ||||||
| DOI: | 10.1109/itw48936.2021.9611438 | ||||||
| Record Number: | CaltechAUTHORS:20220105-582974400 | ||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20220105-582974400 | ||||||
| Official Citation: | J. Sima, F. Zhao and S. -L. Huang, "Exact Recovery in the Balanced Stochastic Block Model with Side Information," 2021 IEEE Information Theory Workshop (ITW), 2021, pp. 1-6, doi: 10.1109/ITW48936.2021.9611438 | ||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
| ID Code: | 112714 | ||||||
| Collection: | CaltechAUTHORS | ||||||
| Deposited By: | Tony Diaz | ||||||
| Deposited On: | 09 Jan 2022 21:36 | ||||||
| Last Modified: | 25 Jul 2022 23:14 |
Repository Staff Only: item control page
