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 | Size | Format | |
---|---|---|---|

aarslan.pdf | 385.92 kB | Adobe PDF | Request a copy |

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