Consistent Recovery Threshold of Hidden Nearest Neighbor Graphs
Consistent Recovery Threshold of Hidden Nearest Neighbor Graphs
Motivated by applications such as discovering strong ties in social networks and assembling genome subsequences in biology, we study the problem of recovering a hidden 2k-nearest neighbor (NN) graph in an n-vertex complete graph, whose edge weights are independent and distributed according to Pn for edges in the hidden 2k-NN …