Revealing Network Connectivity from Response Dynamics

We present a method to infer the complete connectivity of a network from its stable response dynamics. As a paradigmatic example, we consider networks of coupled phase oscillators and explicitly study their long-term stationary response to temporally constant driving. For a given driving condition, measuring the phase differences and the collective frequency reveals information about how the units are interconnected. Sufficiently many repetitions for different driving conditions yield the entire network connectivity (the absence or presence of each connection) from measuring the response dynamics only. For sparsely connected networks, we obtain good predictions of the actual connectivity even for formally underdetermined problems.

Figure 1

Driving induces phase patterns, implicitly defined by (2). The network has $N=16$ units, each connected with a coupling strength $J_{ij}=1/k_i$ to $k_i\equiv 8$ randomly selected others ($J_{ij}=0$ otherwise). (a) Homogeneous frequencies, ${\omega }_i\equiv 1$; (b) heterogeneous random frequencies ${\omega }_i\in [0.1,1.1]$. The phase differences $\Delta {\varphi }_i≔\underset{j}{max}\{{\varphi }_j\}-{\varphi }_i$ in the stationary states are plotted versus $i$. The responses to three different driving conditions—(blue ◯) one unit $i=5$ driven, $I_{5,1}=0.3$; (red ◯) two units $i\in \{2,8\}$ driven, $I_{2,2}=I_{8,2}=0.3$; (gray ●) all units driven by a signal of random strength $I_{i,3}\in [0,0.3]$—are shown along with the undriven dynamics (×).

Figure 2

Inferring connectivity from measuring response dynamics. $M=N=16$ experiments [29]. (a),(b) Connectivities of the networks with homogeneous and heterogeneous natural frequencies of Figs. 1a, 1b, respectively, as reconstructed using Eqs. (5, 6, 7). The matrix of off-diagonal connection strengths ${\widehat{J}}_{ij}$ is gray-coded from light gray (${\widehat{J}}_{ij}=0$) to black (${\widehat{J}}_{ij}=\underset{i^{\prime },j^{\prime }}{max}\{{\widehat{J}}_{i^{\prime }{j}^{\prime }}\}$). Insets: Elementwise absolute difference $|J_{ij}^{\mathrm{original}}-J_{ij}^{\mathrm{derived}}|$, plotted on the same scale.

Figure 3

Revealing connectivity with $M<N$ experiments. Network ($N=64$, $k_i\equiv 10$, ${\omega }_i\equiv 1$) reconstructed by minimizing the 1-norm, (a) $M=38$ and (b) $M=24$. The insets are as in Fig. 2.

Figure 4

Quality of reconstruction and required number of experiments. (a) Quality of reconstruction ($\alpha =0.95$) for $k=10$ and $N=24$ (⋄), $N=36$ (▵), $N=66$ ($\circ$), and $N=96$ (◯). (b) Minimum number of experiments required ($q=0.98$, $\alpha =0.95$) versus network size $N$ with best linear and logarithmic fits (gray and black solid lines). The inset shows same data with $N$ on logarithmic scale.