• Login
    View Item 
    •   Treasures Home
    • Academic Schools and Programs
    • Erik Jonsson School of Engineering and Computer Science
    • JECS Faculty Research
    • Nosratinia, Aria
    • View Item
    •   Treasures Home
    • Academic Schools and Programs
    • Erik Jonsson School of Engineering and Computer Science
    • JECS Faculty Research
    • Nosratinia, Aria
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Side Information in Recovering a Single Community: Information Theoretic Limits

    Thumbnail
    View/Open
    Link to Article (164.1Kb)
    Author
    Saad, Hussein
    Nosratinia, Aria
    Metadata
    Show full item record
    Abstract
    Abstract
    In 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.
    Description
    Full text access from Treasures at UT Dallas is restricted to current UTD affiliates (use the provided Link to Article).
    URI
    https://hdl.handle.net/10735.1/6911
    Collections
    • Nosratinia, Aria

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of TreasuresCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Login

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV