(a) Dispersion relation for Gierer-Meinhardt (reaction-diffusion) dynamics on an Erdös-Rényi graph of nodes and edges, using the same parameters as in Fig. . The dispersion relation indicates the relation between the growth rates (representing dynamics) and the graph eigenvalues (representing network topology). In this case, Turing patterns are driven by the five unstable modes verifying . (b) Distribution of the correlations between the graph eigenvectors and a single Turing pattern for the same graph and parameters as in (a), as a function of the corresponding eigenvector index.

ROC curves of the reconstruction of an Erdös-Rényi graph of nodes and edges. We infer the original graph structure after random deletion of of all network edges, using: a set of five nonadjacent eigenvectors from the intervals (blue curve with ), (orange curve with ), (green curve with ), (red curve with ) or the latter set after swapping and of the inferred graph adjacency matrix (purple curve with ). The grey line indicates random predictions, curves covering an area superior (respectively, inferior) to it, meaning (respectively, ) correspond to better (respectively, worse) than random predictions.

AUC estimation of the reconstruction of an Erdös-Rényi of nodes and edges, as a function of the percentage of deleted edges. We run a Gierer-Meinhardt model with kinetic parameters obtained via the selection scheme from [] (here, and , and diffusion parameters and ) in order to excite a narrow range of the graph eigenvectors around the mode . We obtain five Turing patterns and use them to infer the original graph structure after random deletion of a single edge and up to of all the network edges. This process is repeated for a iterations. The resulting AUCs are depicted as a band (standard deviation) of which average is indicated by a line within it (blue). These values are compared with those drawn from pairwise correlations (orange).

AUC estimation of the reconstruction of an Erdös-Rényi graph of nodes and edges, as a function of the number of patterns used. Parameters for the Gierer-Meinhardt model are the same in Fig. . We obtain Turing patterns and use them to infer the original graph structure after random deletion of of all the network edges. This process is repeated for a iterations. The resulting AUCs are depicted as a band (standard deviation) of which average is indicated by a lighter color.

AUC estimation of the reconstruction of three different network architectures: A regular random graph of nodes, degree , and edges, an Erdös-Rényi graph of nodes and edges, and a scale-free graph of nodes, attachment parameter and edges. In all three cases, the method is applied after random deletion of of all network edges and taking as input a moving interval of five eigenvectors. The resulting AUCs are depicted as bands (standard deviation) of which average is indicated by a line within each band. The grey line indicates random predictions.

Coefficient matching panel: (a) AUC estimation of the reconstruction of three Erdös-Rényi graphs of nodes and degrees as a function of the percentage of deleted edges. In each case, we use a set of five eigenvectors randomly picked from the interval . We infer the original graph structure after random deletion of a single edge and up to of all network edges. Each case (blue, orange and green lines) is then compared with a benchmark trials where we do not match eigenvalues but use random numbers between and 0 as coefficients (blue, orange and green bands). (b) AUC estimation of the reconstruction of an Erdös-Rényi graph of nodes and edges, as a function of the percentage of deleted edges. Parameters for the Gierer-Meinhardt model are the same as in Figs.  and . We obtain five Turing patterns and use them to infer the original graph structure after random deletion of a single edge and up to of all the network edges (line). Benchmark comparison is performed as in (a). (c) Levenshtein edit-distance [] between the sequence of matched eigenvectors indices and the ideal sequence of as a function of the percentage of deleted edges. We consider the same regular random graph as in (a) and (b). The Levenshtein edit-distance between two sequences measures the minimal number of single-character edits needed to transform one into another. Thus, its maximum possible value is equal to the length of the considered sequence which is, in this case, . As a benchmark test assessing the precision of index matching, the Levenshtein edit-distance relative to the matched indices (blue) is compared, at each step of the deletion process, with the same distance relative to a random sequence of integers between 1 and (orange). (d) Coefficient drift as a function of the percentage of deleted edges for the same Erdös-Rényi graph as in (a) and (b).

Performance panel of graph reconstruction of: (1) an Erdös-Rényi graph of nodes, edges and density on which we run a Gierer-Meinhardt model with kinetic parameters and , and diffusion parameters and , in order to excite a narrow range of the graph eigenvectors around the mode . We obtain five Turing patterns and use them to infer the original graph structure after random deletion of of all the network edges. (a1) Histogram of the inferred adjacency matrix elements for . (b1) ROC curves: true positive rates as a function of false positive rates. (c1) Sensitivity and specificity as a function of the applied threshold. (2) an Erdös-Rényi graph of nodes, edges and density on which we run a Gierer-Meinhardt model with kinetic parameters and , and diffusion parameters and , in order to excite a narrow range of the graph eigenvectors around the mode . We obtain five Turing patterns and use them to infer the original graph structure after random deletion of of all the network edges. (a2) Histogram of the inferred adjacency matrix elements for . (b2) ROC curves: true positive rates as a function of false positive rates. (c2) Sensitivity and specificity as a function of the applied threshold. The prediction of missing links requires the selection of discrimination thresholds for the inferred adjacency matrix elements . In the two present examples, we select four thresholds, depicted as vertical lines: and are chosen arbitrarily, is the threshold approximating the original graph connectivity, assuming this is known empirically, and is the threshold maximizing the Youden's index, that is, the sum of sensitivity and specificity [].

AUC estimation of the reconstruction of: (a) Three regular random graphs of nodes, degree , and edges, as a function of the percentage of deleted edges. In each case and for a iterations each, we use a set of five eigenvectors randomly picked from the interval . We infer the original graph structures after random deletion of a single edge and up to of all network edges. For each graph, the resulting AUCs are depicted as bands (standard deviation) of which average is indicated by a line within each band. These values are compared with those drawn from pairwise correlations, depicted in corresponding pale colors. (b) Three scale-free graphs of nodes, attachment parameter , and edges, as a function of the percentage of deleted edges. In each case and for a iterations each, we use a set of five eigenvectors randomly picked from the interval . We infer the original graph structures after random deletion of a single edge and up to of all network edges. For each graph, the resulting AUCs are depicted as bands (standard deviation) of which average is indicated by a line within each band. These values are compared with those drawn from pairwise correlations, depicted in corresponding pale colors.