Abstract: 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 nearest neighbor (NN) graph in a random complete graph, whose edge weights are independent and distributed according to P for edges in the hidden NN graph and Q otherwise. This model incorporates the celebrated Watts-Strogatz small-world graph as a special case. For both the exact and almost exact recovery problems, we characterize the sharp…