We propose an efficient and accurate way of predicting the connectivity of neural networks in the brain represented by simulated calcium fluorescence data. Classical methods to neural network reconstruction compute a connectivity matrix whose entries are pairwise likelihoods of directed excitatory connections based on time-series signals of each pair of neurons. Our method uses only a fraction of this computation to achieve equal or better performance. The proposed method is based on matrix completion and a local thresholding technique. By computing a subset of the total entries in the connectivity matrix, we use matrix completion to determine the rest of the connection likelihoods, and apply a local threshold to identify which directed connections exist in the underlying network. We validate the proposed method on a simulated calcium fluorescence dataset. The proposed method outperforms the classical one with 20% of the computation.