The problem of reconstructing nonlinear and complex dynamical systems from available data or time series is prominent in many fields, including engineering, physical, computer, biological, and social sciences. Many methods have been proposed to address this problem and their performance is satisfactory. However, none of them can reconstruct network structure from large-scale real-time streaming data, which leads to the failure of real-time and online analysis or control of complex systems. In this article, to overcome the limitations of current methods, we first extend the network reconstruction problem (NRP) to online settings, and then develop a follow-the-regularized-leader (FTRL)-Proximal style method to address the online complex NRP; we refer to it as Online-NR. The performance of Online-NR is validated on synthetic evolutionary game network reconstruction datasets and eight real-world networks. The experimental results demonstrate that Online-NR can effectively solve the problem of online network reconstruction with large-scale real-time streaming data. Moreover, Online-NR outperforms or matches nine state-of-the-art network reconstruction methods.