Skip navigation
Please use this identifier to cite or link to this item:
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].
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    Request a copy

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