CaltechAUTHORS
  A Caltech Library Service

Exact Recovery in the Balanced Stochastic Block Model with Side Information

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:
URLURL TypeDescription
http://doi.org/10.1109/itw48936.2021.9611438DOIArticle
ORCID:
AuthorORCID
Sima, Jin0000-0003-4588-9790
Additional Information:© 2021 IEEE.
DOI:10.1109/itw48936.2021.9611438
Record Number:CaltechAUTHORS:20220105-585060800
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:09 Jan 2022 21:36

Repository Staff Only: item control page