Inferring missing edges in a graph from observed collective patterns.

Many real-life networks are incomplete. Dynamical observations can allow estimating missing edges. Such procedures, often summarized under the term 'network inference', typically evaluate the statistical correlations among pairs of nodes to determine connectivity. Here, we offer an alternative approach: completing an incomplete network by observing its collective behavior. We illustrate this approach for the case of patterns emerging in reaction-diffusion systems on graphs, where collective behaviors can be associated with eigenvectors of the network's Laplacian matrix. Our method combines a partial spectral decomposition of the network's Laplacian matrix with eigenvalue assignment by matching the patterns to the eigenvectors of the incomplete graph. We show that knowledge of a few collective patterns can allow the prediction of missing edges and that this result holds across a range of network architectures. We present a numerical case study using activator-inhibitor dynamics and we illustrate that the main requirement for the observed patterns is that they are not confined to subsets of nodes, but involve the whole network.