extfieldsofstudy: Mathematics Medicine Physics

s2fieldsofstudy:
Computer Science
Mathematics

text:
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).


Research Collaboration Between a Small Technology Company and Universities: Results, Opinions, and Conclusions

: The incentives for research collaboration between industry and academia are discussed. The problems and the lessons learnt during several projects are analyzed, both from a university and an industry point of view. In the second part, the results of a big collaborations project between Solvias and several universities are shown, and the significant addition of know-how to the Solvias Toolbox will be addressed. Finally, the focus for the future catalysis research in Solvias is described. Abstract: On June 25, 2001, Prof. Dr. Franr;ois L'Eplattenier presented the first 'Solvias Leading Scientist' award to Dr. Benoit Pugin, Solvias AG.

Introduction
As pointed out in the introductory text and also in the address of F. L'Eplattenier, science is an important basis for a technology company such as Solvias. Obviously carrying out research is expensive and Solvias no longer has the resources it used to have when it was still part of Ciba-Geigy or Novartis, and this limited R&D budget has to be managed very carefully. On the other hand, Solvias now has more freedom to focus research as it sees fit and in addition there is very high flexibility for research collaborations with various partners. In particular, collaborations with universities can be beneficial for both partners if it is done right. In addition, both national and international agencies are often willing to support such cooperations when small companies are involved. In this contribution we will discuss briefly some experi- The TAB project was a team effort between our industrial catalysis research group and three universities. The areas investigated were C-C coupling, oxidation, and ligand synthesis. We had installed a formal project organization with the Technology Advisory Board as sponsor and a steering committee consisting of A. Togni, M. Beller, J. Backvall, H.U. Blaser (head) and M. Studer (who was also the operational project leader). The three subprojects were headed by senior Solvias scientists. In addition we also had internal consultants from the research and development departments of the Novartis Pharma and Agro divisions in order to provide input on the needs of our customers. During about four years, three Ph.D. thesis, two postdocs and several internal teams were sponsored. Regular meetings took place between all teams, the steering group, and the consultants to present, discuss, and assess the results and recommend priorities for further work. These efforts significantly enlarged the Solvias Catalysis Toolbox and up to now have resulted in seven publica-tions (with many more planned), three patent applications, and several poster presentations.
Last but not least, two technical processes were realized based on the know-how gathered within this project.

Incentives and Ways to Collaborate
What is the motivation for cooperation between industry and academic groups? The following points come to mind: -Access to new ideas. This is especially important for smaller industrial research units limited to selected fields of expertise. -Access to know-how and new technical methods. -Universities are interested in relevant problems and contacts (and also the money). -Possible source for good job candidates for industry. -Resources at universities are relatively inexpensive (compared to industrial research) and funding is sometimes available. -Last but not least: It's fun! There are many ways and forms to organize interactions and collaboration between industry and universities. Each has positive and negative aspects as can be seen in Table 1.

Type of collaboration
Advantages Disadvantages In his lecture, A. Togni described important results obtained during several research collaboration with industry and formulated and commented on seven theses concerning what he has learnt from these undertakings. We list these without much further comment: Thesis 1. The purpose of collaboration between academic institutions and industry, in terms of common research projects and/or consulting relationships, is the basic advancement in a specific area of common (shared) scientific interest.
Thesis 2. The partners should be concerned about the real mutual benefits of a collaboration and should clearly define goals.
-Academics: Resist the temptation of engaging in collaborative work with industry primarily because it provides extra research funding. -Industry: Do not finance projects at an academic institution just because the manpower is cheaper. Thesis 3. The immediate function of the consulting academic partner is not to provide solutions to the most pressing problems an industrial laboratory may have.
Thesis 4. Collaboration with different companies is conceivable. In this case, different non-interacting research areas should be chosen in order to avoid possible conflicts of interest.
Thesis 5. The relationship between academic and industrial partners is based upon trust. Trust derives from a functioning communication between colleagues.
Thesis 6. The goals of a shared project should clearly be formulated by the academic partner, who also takes the responsibility of supervising and mentoring the students involved.
Thesis 7. The timely publication of research results is both a duty and a fundamental freedom for the academic partner. Publications should not be drastically delayed or even thwarted by the industrial partner.
Interestingly, these theses are in amazing agreement with the summary presented by M. Studer from the Solvias' point of view. His conclusions on how to make a collaboration more productive and/or less frustrating were as follows: -An informal or loose cooperation is only advisable if a very good relation with the partner already exists. Results from the Current Collaboration will help to understand what can reasonably be expected from the academic partner (very often it is more than one thinks). -Be open for changes in the goals. The more ambitious the goals, the more likely that they will not be attained in a linear fashion. -Even though organization was much more demanding, the TAB Project showed us that networks of this sort have significant synergies. -Last but not least: Be prepared to invest not just some money but a lot of management energy as well! As a general conclusion, it can be stated that a good collaboration needs a clear definition and the willingness to invest a lot of energy, good will and some money.
Let's come back to the successful TAB Project. Obviously, research at Solvias has the one and only goal of gaining a competitive advantage by offering better services to our customers. In the field of catalysis and synthesis this means that we have to be able to -make a fast and accurate assessment of a specific customer problem and make a suitable offer to show the feasibility of our proposal, in a time and cost effective manner, -be able to develop a technically feasible synthesis or catalytic method, -attain high success rates. These abilities were considerably improved through the project. Table 2 gives our assessment of how the Solvias Catalysis Toolbox has benefited from the results and contributions of the TAB Project.
Where is Catalysis Research at Solvias heading in the near future? On the one hand Solvias has reduced the number of research topics and will focus on chiral ligand synthesis, asymmetric reductions, and modified heterogeneous catalysts. On the other hand, more new methods with high synthetic potential will be established, in order to be ready to tackle any synthetic problem in fine chemical synthesis. The Scientific Advisory Board members A. Pfaltz and A. Togni will help us to make the right choices. and carbonylation reactions · Direct method for 1 0 amide synthesis · New catalysts and precursors KTI (Commission for Technology and Innovation); similarly we have initiated a Oxidation · Know-how in dehydro-· Assessment of area joint research project with Ciba LSM on genation and other selected · Know-how in the oxidation of a similar topic. At the moment M. Studer oxidation reactions benzylic carbon atoms and of alcohols is also actively involved in the discussion Immob. I funct.
· Better than state of the art · New functionalized ligand classes on the role of catalysis within the sixth Ligands technology EU framework program. Fast Screening · State of the art equipment, · Improvement of equipment efficient screening · Improvement of productivity