Side Information in Recovering a Single Community: Information Theoretic Limits

dc.contributor.authorSaad, Hussein
dc.contributor.authorNosratinia, Aria
dc.contributor.utdAuthorSaad, Hussein
dc.contributor.utdAuthorNosratinia, Aria
dc.date.accessioned2019-09-27T15:52:25Z
dc.date.available2019-09-27T15:52:25Z
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 Article).
dc.description.abstractIn this paper, we study the effect of side information on the information limits of recovering a hidden community of size K inside a graph consisting of n nodes with K = o(n). Side information for each node in the graph is modeled by a random vector whose components have finite cardinality. The variation in quantity of side information as a function of graph size n is represented by varying the size of the vector of side information while keeping the log-likelihood ratio (LLR) of each component with respect to the node labels fixed. We show when and by how much side information can improve the information limits of weak and exact recovery by providing tight necessary and sufficient conditions for both weak and exact recovery. Furthermore, we show that, under certain conditions, any algorithm achieving weak recovery can also achieve exact recovery if followed by a local voting procedure. © 2018 IEEE.
dc.description.departmentErik Jonsson School of Engineering and Computer Science
dc.description.sponsorshipThis work was supported in part by the NSF grant 1718551.
dc.identifier.bibliographicCitationSaad, H., and A. Nosratinia. 2018. "Side Information in Recovering a Single Community: Information Theoretic Limits." Proceedings of the IEEE International Symposium on Information Theory: 2107-2111, doi: 10.1109/ISIT.2018.8437517
dc.identifier.isbn9781538647806 (ISBN)
dc.identifier.urihttps://hdl.handle.net/10735.1/6911
dc.language.isoen
dc.publisherInstitute of Electrical and Electronics Engineers Inc.
dc.relation.urihttp://dx.doi.org/10.1109/ISIT.2018.8437517
dc.rights©2018 IEEE
dc.source.journalProceedings of the IEEE International Symposium on Information Theory
dc.subjectStochastic processes
dc.subjectInformation theory
dc.subjectComputational complexity
dc.subjectGraph theory
dc.titleSide Information in Recovering a Single Community: Information Theoretic Limits
dc.type.genrearticle

Files

Original bundle

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

Collections