Figure 1

Schematic illustration of our binary-state network reconstruction methodology based on statistical inference. In this example, the data are collected by implementing the voter model on an empirical network—the Zachary karate-club network, where initially 30% of the nodes are randomly set to state 1. (a) The actual structure of the network. (b) The data matrix, where each row is a time string representing all nodes' states at that time step and each column is a node's state at different time steps. The black and blank squares denote the 1 and 0 state, respectively. Say we wish to ascertain all neighbors of node 33 (highlighted by the red frame), so only the strings with ${\mathrm{\Psi }}_{33}^t=0$ and its next string at $t+1$ are used. Each pair of useful strings are highlighted by a frame with a different color. The quantity $P_{16}^{33}$ is the probability of the event $s_{33}(t+1)=1$ under the prior conditions of $s_{16}\left(t\right)=1$ and $s_{33}\left(t\right)=0$. We have $P_{16}^{33}=2/3$ for this example (highlighted by the blue frame). (c) The values of $P_{i\to 33}$ are obtained through the EM algorithm, where only the nonzero values of the probability are shown. The neighbors of node 33 in the network are shown in the lower right corner (marked by light-red color). (d) The values of $P_{i\to j}$ for each node $j$, where the red nodes and blue points denote the actual and nonexistent links, respectively. The red dashed line represents the threshold $\mathrm{\Delta }=1/N$ for determining whether a reconstructed value $P_{i\to j}$ can be regarded as representing an actual link or a null link. (e) If we choose $\mathrm{\Delta }=0$, there are eight false links as predicted (marked by the red links in the network). However, for $\mathrm{\Delta }=1/N$, all actual links are correctly inferred.