Reconstructing network topology and coupling strengths in directed networks of discrete-time dynamics

Reconstructing network connection topology and interaction strengths solely from measurement of the dynamics of the nodes is a challenging inverse problem of broad applicability in various areas of science and engineering. For a discrete-time step network under noises whose noise-free dynamics is stationary, we derive general analytic results relating the weighted connection matrix of the network to the correlation functions obtained from time-series measurements of the nodes for networks with one-dimensional intrinsic node dynamics. Information about the intrinsic node dynamics and the noise strengths acting on the nodes can also be obtained. Based on these results, we develop a scheme that can reconstruct the above information of the network using only the time-series measurements of node dynamics as input. Reconstruction formulas for higher-dimensional node dynamics are also derived and illustrated with a two-dimensional node dynamics network system. Furthermore, we extend our results and obtain a reconstruction scheme even for the cases when the noise-free dynamics is periodic. We demonstrate that our method can give accurate reconstruction results for weighted directed networks with linear or nonlinear node dynamics of various connection topologies, and with linear or nonlinear couplings.

Figure 1

Verification of the reconstruction formulas for the directed weighted random network. Heterogeneous coupled Logistic map dynamics $f_i\left(x\right)=r_{i}x(1-x)$ with $r_i$ uniformly distributed in (0,0.8] and linear couplings. (a) ${\left({\mathbf{K}}_1{\mathbf{K}}_0^{-1}\right)}_{ij}$. (b) ${\left({\mathbf{K}}_2{\mathbf{K}}_1^{-1}\right)}_{ij}$ vs the actual $N_{ij}$, verifying (14). $T_{\text{av}}={10}^6$. (c) ${\left({\mathbf{K}}_2{\mathbf{K}}_1^{-1}\right)}_{ij}$ vs the actual $N_{ij}$, with $T_{\text{av}}=7\times {10}^6$. (d) ${({\mathbf{K}}_0-{\mathbf{K}}_1{\mathbf{K}}_0^{-1}{\mathbf{K}}_1^{⊺})}_{ii}$ vs the actual ${\sigma }_{ii}$, verifying (15). $T_{\text{av}}={10}^6$.

Figure 2

Reconstruction for a directed weighted random network with heterogeneous coupled logistic map dynamics $f_i\left(x\right)=r_{i}x(1-x)$ and linear couplings as in Fig. 1. $T_{\text{av}}={10}^6$. (a) Reconstructed $W_{ij}$ using (17) vs the actual $W_{ij}$. (b) The reconstructed $f_i^{\prime }$ using (18) vs the actual $f_i^{\prime }$.

Figure 3

Reconstruction of the directed weighted network for various nonlinear coupling functions as described in the text. Heterogeneous coupled logistic map dynamics. $T_{\text{av}}={10}^6$. (a) Reconstructed relative weights using (19) vs the actual ones. (b) Reconstructed $f_i^{\prime }$ using (18) vs the actual ones.

Figure 4

Network reconstruction performance as a function of the measurement time $T_{\text{av}}$. The rms errors for reconstruction of $W_{ij}$ and $f_i^{\prime }$ using the formulas in Eqs. (17) and (18) without employing the method of clustering into connected and unconnected groups are denoted by ${\delta }_W$ and ${\delta }_{f^{\prime }}$, respectively, showing the expected $1/\sqrt{T_{\text{av}}}$ behaviors (solid green lines). The corresponding rms errors when $W_{ij}$ are clustered into two groups of connected and unconnected ones are denoted by ${\mathrm{\Delta }}_W$ and ${\mathrm{\Delta }}_{f^{\prime }}$, respectively, showing even lower rms errors (dashed blues lines). The WR1 network ($N=100$) with heterogeneous logistic node dynamics with linear couplings distributed with two Gaussians with means 0.1 and $-0.1$ (with relative fractions of 0.8 and 0.2, respectively), and standard deviations 0.02.

Figure 5

Network reconstruction for networks of different topologies. $N=100$ networks with heterogeneous logistic node dynamics with linear couplings distributed with two Gaussians with means 0.05 and $-0.05$ (with relative fractions of 0.8 and 0.2, respectively), and standard deviations 0.01. $T_{\text{av}}={10}^6$. Scale-free bidirectional network with mean degree =5.68: (a) Reconstructed $W_{ij}$ vs the actual $W_{ij}$, (b) reconstructed $f_i^{\prime }$ using vs the actual $f_i^{\prime }$. Small-world bidirectional network with mean degree =6 and rewiring probability $\beta =0.02$: (c) Reconstructed $W_{ij}$ vs the actual $W_{ij}$, (d) reconstructed $f_i^{\prime }$ using vs the actual $f_i^{\prime }$. (e) Reconstruction errors ${\mathrm{\Delta }}_W$ and ${\mathrm{\Delta }}_{f^{\prime }}$ of small-world networks (mean degree =6) vs the rewiring probability $\beta$.

Figure 6

Reconstruction of the directed weighted network with intrinsic node dynamics given by the heterogeneous Hénon map: $u_i(n+1)=1+v_i\left(n\right)-a_i{u}_i^2, v_i(n+1)=b{u}_i\left(n\right)$ with $b=0.3$ and $a_i$ uniformly distributed in $(-0.132,-0.11]\times (1-b^2)$, and linear couplings. $T_{\text{av}}={10}^7$. (a) ${\left({\mathbf{K}}_1{\mathbf{K}}_0^{-1}\right)}_{ij}$ vs the actual $M_{ij}$, verifying the reconstruction formula (28). (b) The reconstructed $W_{ij}$ using (24) vs the actual $W_{ij}$. (c) The reconstructed ${\sigma }_{ii}$ using (29) vs the actual ${\sigma }_{ii}$. (d) The reconstructed partial derivative matrix elements using (23) and (28) vs the actual ones.

Figure 7

Verification of the reconstruction formulas for the directed weighted network having period-2 noise-free dynamics. Heterogeneous coupled Hill map dynamics and linear couplings. $T_{\text{av}}={10}^6$. (a) The noise-free periodic point $X_i^{\left(k\right)}$ vs ${\langle x_i\rangle }_k$, verifying (37). (b) ${\left({\mathbf{K}}_1^{\left(1\right)}{{\mathbf{K}}_0^{\left(1\right)}}^{-1}\right)}_{ij}$ vs the actual ${\mathcal{N}}_{ij}+f_i^{\prime }\left({\langle x_i\rangle }_1\right){\delta }_{ij}$, verifying (45) for $k=1$. (c) ${\left({\mathbf{K}}_1^{\left(2\right)}{{\mathbf{K}}_0^{\left(2\right)}}^{-1}\right)}_{ij}$ vs the actual ${\mathcal{N}}_{ij}+f_i^{\prime }\left({\langle x_i\rangle }_2\right){\delta }_{ij}$, verifying (45) for $k=2$.

Figure 8

Network reconstruction for period-2 noise-free dynamics for the same system in Fig. 7. (a) Naive use of the reconstruction formula for stationary noise-free dynamics in reconstructing $W_{ij}$ using (17). (b) Naive use of the reconstruction formula for stationary noise-free dynamics in reconstructing $f_i^{\prime }$ using (18). (c) Naive use of the reconstruction formula for stationary noise-free dynamics ${\sigma }_{ii}$ using (15). (d) Reconstructed $W_{ij}$ using (46) for periodic dynamics vs the actual $W_{ij}$. (e) The reconstructed partial derivative matrix elements using (47) for periodic dynamics vs the actual ones. (f) The reconstructed ${\sigma }_{ii}$ using (44) for periodic dynamics vs the actual ${\sigma }_{ii}$.