Measuring Entropy of Binary Node Labels Given Noisy Edge Measurements in Erdos-Renyi Graphs

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].