Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01n583xx62m
 Title: Measuring Entropy of Binary Node Labels Given Noisy Edge Measurements in Erdos-Renyi Graphs Authors: Arslan, Andre Advisors: Abbe, Emmanuel A. Contributors: Singer, Amit Department: Mathematics Class Year: 2017 Abstract: Given an Erdos-Renyi graph G G(n; p), independently assign each vertex a hidden binary label, each of the two labels equally likely. Based on these labels, noisy observations are made of whether each edge connects two vertices of the same label or different labels, each observation independently and randomly incorrect with noise parameter " 2 (0; 1=2). When is it possible to recover the hidden binary labels given only the graph and the edge observations? Sections 1 and 2 set up motivation for the problem. [ABBS14] nds an asymptotically tight condition for when exact recovery is possible given a fixed ", outlined in Section 3. Section 4 deals with the giant component regime, G(n; c=n) for c > 1, where exact recovery is not possible. The main result in this section bounds the remaining entropy of the binary node labels (given the graph and edge observations) as a fraction of n. Section 5 uses numerical simulations to plot the bound for various c over the range " 2 [0; 1=2]. URI: http://arks.princeton.edu/ark:/88435/dsp01n583xx62m Type of Material: Princeton University Senior Theses Language: en_US Appears in Collections: Mathematics, 1934-2020

Files in This Item:
File SizeFormat
aarslan.pdf385.92 kBAdobe PDF

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.