  In this paper, we study detection and fast reconstruction of the celebrated
Watts-Strogatz (WS) small-world random graph model \citep{watts1998collective}
which aims to describe real-world complex networks that exhibit both high
clustering and short average length properties. The WS model with neighborhood
size $k$ and rewiring probability probability $\beta$ can be viewed as a
continuous interpolation between a deterministic ring lattice graph and the
Erd\H{o}s-R\'{e}nyi random graph. We study both the computational and
statistical aspects of detecting the deterministic ring lattice structure (or
local geographical links, strong ties) in the presence of random connections
(or long range links, weak ties), and for its recovery. The phase diagram in
terms of $(k,\beta)$ is partitioned into several regions according to the
difficulty of the problem. We propose distinct methods for the various regions.
