We consider the problem of learning the structure of ferromagnetic Ising
models Markov on sparse Erdos-Renyi random graph. We propose simple local
algorithms and analyze their performance in the regime of correlation decay. We
prove that an algorithm based on a set of conditional mutual information tests
is consistent for structure learning throughout the regime of correlation
decay. This algorithm requires the number of samples to scale as \omega(\log
n), and has a computational complexity of O(n^4). A simpler algorithm based on
correlation thresholding outputs a graph with a constant edit distance to the
original graph when there is correlation decay, and the number of samples
required is \Omega(\log n). Under a more stringent condition, correlation
thresholding is consistent for structure estimation. We finally prove a lower
bound that \Omega(c\log n) samples are also needed for consistent
reconstruction of random graphs by any algorithm with positive probability,
where c is the average degree. Thus, we establish that consistent structure
estimation is possible with almost order-optimal sample complexity throughout
the regime of correlation decay.