Evolutionary reconstruction of networks

Can a graph specifying the pattern of connections of a dynamical network be reconstructed from statistical properties of a signal generated by such a system? In this model study, we present an evolutionary algorithm for reconstruction of graphs from their Laplacian spectra. Through a stochastic process of mutations and selection, evolving test networks converge to a reference graph. Applying the method to several examples of random graphs, clustered graphs, and small-world networks, we show that the proposed stochastic evolution allows exact reconstruction of relatively small networks and yields good approximations in the case of large sizes.

In this Letter, we present an evolutionary algorithm and apply it to reconstruct graphs from their Laplacian spectra. Random graphs, small-world networks and networks with cluster organization are considered. We show that for relatively small graphs, exact reconstruction within a reasonable evolution time is possible. For larger graphs, the evolution leads to a network which provides a good approximation of the target graph. Both the spectral properties as well as other characteristic features of the reference network, such as the diameter, clustering coefficient, and the average degree, are well reproduced by the approximately reconstructed graph.
Any graph G can be described by its adjacency matrix A such that A ij = 1 if the nodes i and j are connected, and A ij = 0 otherwise. A Laplacian spectrum of the graph G is defined [4] as the set of eigenvalues λ i of the matrix T with elements T ij = A ij − m i δ ij where m i = N j=1 A ij is the degree of node i and δ ij is the Kronecker symbol.
Laplacian spectra are closely related to dynamical properties of a simple network: Consider a hypothetical linear "molecule" consisting of N identical particles connected by identical elastic strings. The pattern of connections is defined by a graph G: a bond between particles i and j in the network is present if the respective element A ij in the adjacency matrix of the graph G is equal to unity and absent otherwise. This dynamical system is described by a set of differential equations Obviously, the vibration frequencies ω k of such a molecule (k = 0, 1, . . . , N − 1) are given by the eigenvalues λ k = −ω 2 k of the matrix T. Note that one eigenvalue λ 0 always satisfy λ 0 = 0 due to the translational invariance of this equation. For this reason, the Laplacian spectra of a graph are also known as the vibrational spectra [4]. Besides yielding a link to dynamical networks, spectra provide a powerful invariant characterization of graphs. Each graph of size N is thus mapped into a set of N − 1 positive real numbers ω i . Various statistical properties of graphs can be expressed or evaluated in terms of their spectra [4]. Moreover, even though cospectral graphs (topologically different graphs with the same spectra) are known to exist, their fraction is very small [20]. Hence, with a high probability two graphs with coinciding spectra would indeed be identical.
It is convenient to introduce the spectral density ρ(ω) for a graph as a sum of narrow Lorentz distributions with the same width γ and the normalization constant C chosen in such a way that ∞ 0 ρ(ω)dω = 1. The spectral distance ǫ between two graphs G and G 0 with densities ρ(ω) and ρ 0 (ω) can then be defined as Our aim is to reconstruct graphs from their Laplacian spectra. Note that the number M N of different graphs of a given size N becomes (super)astronomically large even for relatively small sizes. A lower bound for M N is 2 N (N −1)/2 /N !, so even for N = 50 we have M N > 1.9 × 10 304 . Therefore, finding an exact solution to the inverse problem by subsequently testing all graphs is in practice impossible. Instead, we shall use an evolutionary procedure for graph reconstruction.
Suppose that we want to reconstruct a certain reference graph G 0 with the spectral density ρ 0 (ω). In order to do this, we generate an arbitrary initial graph G and introduce a stochastic process of mutations and selection. The mutations represent random modifications of the pattern of connections whereas the selection is based on the spectral distance (2) between two graphs.
A mutation of the graph G first consists of deleting all connections of a randomly chosen node i. A new degree m i for this particular node is then chosen at random between 1 and N − 1 followed by a random generation its m i new connections. The obtained mutated graph is denoted as G ′ .
To decide whether a mutation should be accepted (that is, to realize a selection), we calculate the spectral distance ǫ ′ between the modified graph G ′ and the reference graph G 0 . This is then compared with the spectral distance ǫ between G and G 0 . If ∆ǫ = ǫ ′ − ǫ < 0, the mutation is always accepted. If ∆ǫ > 0, the mutation is accepted with a certain probability p(∆ǫ) = exp(−∆ǫ/ǫθ). When a mutation has been accepted, the graph G is replaced by G ′ .
These two steps are applied iteratively and the evolution is continued until the spectra are identical (ǫ = 0) or the spectral distance ǫ is smaller than a given threshold. Note that mutations may be accepted even if ∆ǫ > 0 to avoid that the evolution gets trapped in a local minimum. The noise of the selection is controlled by the "temperature" parameter θ. The scheme is similar to the Metropolis algorithm used in statistical mechanics and complex combinatorial optimization [17,18].
In the following, this procedure is applied to reconstruct three different types of reference graphs.
Random networks. First we consider the case where the reference network is a random graph of size N and connection probability p. As an example, we take a reference graph G 0 with N = 10 and p = 0.2. The initial graph G init is also random, but has a higher connection probability p = 0.9. The two graphs and their Laplacian spectra are shown in FIG. 1a-b. We then apply the stochastic evolution, described above, with the selection temperature θ = 0.044 . The evolution of the spectral difference ǫ is shown in FIG. 1c. The spectral distance is gradually decreasing, with some fluctuations, until eventually a transition occurs at t ≃ 3500, when the spectral densities of the reference and test graph coincide. Examining the final graph G final in FIG. 1a, we conclude that it is indeed identical to the reference graph G 0 . Note that though the number of graphs of size N = 10 is of the order of 10 6 , the exact reference graph has been reconstructed in only 3500 stochastic iterations.
To determine the reliability of the reconstruction and its dependence on the selection temperature θ, a statistical investigation has been performed. The variation of the mean spectral distance ǫ as a function of θ is shown in FIG. 1d where each point corresponds to the average over 10 3 evolutions each starting from a randomly chosen test graph with connection probability chosen randomly from [0, 1]. Each evolution was terminated after 4 × 10 4 iterations. We see that there is a window of the selection temperature θ where fast convergence takes place. At the minimum θ = 0.04 approx. 92 % of all evolutions converge exactly to the reference graph within the specified time.
Clustered networks. Next, we consider large clustered networks representing a union of several random graphs with different connection densities. As an example, a reference network G 0 of size N = 50 with three clusters of high connection probability is chosen. To prepare it, a sparse random graph of size N with low connection probability p = 0.05 is first generated. Then three random Though exact reconstruction is not reached for the considered large graph, statistical analysis reveals that the properties of the final graph are close to that of the reference graph. FIG. 2b shows the time dependence ǫ(t) of the mean spectral difference averaged over the 10 3 stochastic evolutions. We see that ǫ decreases down to about 0.056 after 10 4 iterations. Other important properties of the reference graph, such as its diameter L, clustering coefficient C, and its mean degree D (all defined as in the review [13]), are also well-reproduced. This is seen from FIG. 2b, where the time dependence of the mean ratios L(t)/L 0 , C(t)/C 0 , and D(t)/D 0 is presented.
Similarity between graphs can also be discussed in terms of their adjacency matrices: For any two graphs G 1 and G 2 with adjacency matrices A 1 and A 2 , a transformation F = F(A 1 , A 2 ) can be introduced as Here the real matrices U 1,2 and V 1,2 are defined by the singular-value decomposition [19]  and G 2 do not coincide, the norm δ = 1/N ( i,j ∆ 2 ij ) 1/2 of this difference can be used as a measure of the distance between the graphs.
In FIG. 3, we visually display the matrices A 0 , where A 0 , A init and A final are the adjacency matrices of the graphs G 0 , G init and G final . Here the elements in the matrices are represented by a square array of pixels using gray-scale color maps whose limits are determined by the minimum and maximum values of the respective matrix elements. Even though the matrix F final does not coincide with A 0 , it is already very close to it. The respective distances δ for the initial and final graphs are δ init = 0.41 and δ final = 0.04.
Small worlds. Now we consider a small-world graph (see [6]) consisting of N = 40 nodes organized on a ring with each node connected to its two neighboring nodes. In addition, each node i is connected to a randomly chosen node j in the network (j = i ± 1) with the probability p = 0.1. The adjacency matrix of this reference graph is visually displayed in the left frame of FIG. 4a. To test the reconstruction efficiency for this graph, we have performed 10 3 stochastic evolutions, each starting from a random graph with connection probability chosen randomly from the interval [0, 1]. The spectra of the reference, initial and final graphs of one particular evolution are shown in FIG. 4b; we see that even fine structures of the reference spectrum have been reproduced. The structure of the final graph is also close to that of the reference graph as seen from the last two frames in FIG. 4a where the matrices F init and F final defined by Eq. (3) are displayed (the respective distances δ for the initial and final graphs are δ init = 0.92 and δ final = 0.01).
The time dependence of the mean spectral distance ǫ(t) and the ratios L(t)/L 0 , C(t)/C 0 , and D(t)/D 0 averaged over 10 3 evolutions is shown in FIG. 4c. After a transient of 10 4 iterations, ǫ = 0.058 and all three ratios have approached unity implying that these characteristic properties of the reference network also are well-captured by the approximate reconstruction process.
Our analysis has revealed that the proposed evolutionary algorithm provides an efficient method for exact or approximate reconstruction of graphs from their Laplacian spectra. Based on the spectral density only, such important properties of the reference network as its di- ameter, clustering coefficient, and average degree are well reproduced. Moreover, approximately reconstructed networks have similar adjacency matrices determining the pattern of connections between nodes. Unique evolutionary reconstruction is not possible for cospectral graphs, but these are, however, extremely rare [3]. Our numerical study has been performed using a fixed selection temperature θ in the evolutionary algorithm; more refined algorithms employing a time dependent temperature (similar to the method of simulating annealing [18]) can also be implemented.
The spectral density (1) of a graph may be interpreted as representing a power spectrum of a certain stochastic signal z(t). This signal can be, for instance, generated by vibrations of a damped elastic "molecule" under action of external white noise. Such a linear dynamical system would be described by the equations where ξ i (t) are independent random forces and A ij is the adjacency matrix of the graph. We have shown that the structure of this simple model system can be reconstructed from its temporal signal z(t) = i a i x i (t) with randomly chosen weights a i . Thus, we see that important network information can be encoded into a stochastic signal and then efficiently recovered from it.
In essence, the proposed stochastic evolution can be regarded as a learning process through which a test network, by adjusting its internal structure, learns to approximate the dynamics generated by a different system. Similar approaches can be applied to solve other problems. For instance, approximations of large clustered graphs by graphs of a smaller size can be constructed, and networks generating stochastic signals with prescribed power spectra can be designed.
The results of our model study put forward questions whether network organization of complex nonlinear dynamical systems with deterministic chaos can be reconstructed from their power spectra in an evolutionary learning process and whether, generally, a nonlinear network may learn to generate given complex chaotic dynamics by iteratively adjusting its pattern of connections. A practical solution of these problems would be important for a variety of applications.
MI acknowledges financial support from the Alexander von Humboldt-Stiftung, Germany, and from the Danish Technical Research Council (grant nr. 9901488).