Belief Propagation with Side Information for Recovering a Single Community

Simple item page
dc.contributor.ORCID0000-0002-3751-0165 (Nosratinia, A)
dc.contributor.VIAF105575689 (Nosratinia, A)
dc.contributor.authorSaad, Hussein
dc.contributor.authorNosratinia, Aria
dc.contributor.utdAuthorSaad, Hussein
dc.contributor.utdAuthorNosratinia, Aria
dc.date.accessioned2019-07-12T20:37:02Z
dc.date.available2019-07-12T20:37:02Z
dc.date.created2018-06-17
dc.descriptionFull text access from Treasures at UT Dallas is restricted to current UTD affiliates (use the provided link to the article). Non UTD affiliates will find the web address for this item by clicking the Show full item record link and copying the "relation.uri" metadata.
dc.description.abstractIn this paper, we study the effect of side information on the recovery of a hidden community of size K inside a graph consisting of n nodes with K=o(n). We focus on side information with finite cardinality and bounded (as nrightarrow propto) log-likelihood ratios (LLRs). We calculate tight necessary and sufficient conditions for weak recovery of the labels subject to observation of the graph and side information under belief propagation (BP). Also, we show that BP with side information is strictly inferior to the maximum likelihood detector without side information. Finally, we validate our results through simulations on finite synthetic data-sets that shows the power of our asymptotic results in characterizing the performance even at finite n.
dc.description.departmentErik Jonsson School of Engineering and Computer Science
dc.description.sponsorshipNSF grant 1718551
dc.identifier.bibliographicCitationSaad, H., and A. Nosratinia. 2018. "Belief propagation with side information for recovering a single community." IEEE International Symposium on Information Theory: 1271-1275, doi:10.1109/ISIT.2018.8437840
dc.identifier.isbn9781538647806
dc.identifier.urihttps://hdl.handle.net/10735.1/6699
dc.language.isoen
dc.publisherInstitute of Electrical and Electronics Engineers Inc.
dc.relation.isPartOfIEEE International Symposium on Information Theory (ISIT)
dc.relation.urihttp://dx.doi.org/10.1109/ISIT.2018.8437840
dc.rights©2018 IEEE.
dc.subjectStochastic models
dc.subjectStochastic systems
dc.subjectTurbo codes (Telecommunication)
dc.subjectDatasets--Synthetic
dc.subjectBack propagation (Artificial intelligence)
dc.titleBelief Propagation with Side Information for Recovering a Single Community
dc.type.genrearticle

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
JECS-6172-279754.72-LINK.pdf
Size:
164.09 KB
Format:
Adobe Portable Document Format
Description:
Link to Article
Download

Collections

Nosratinia, Aria