Colloquium Computer Science, Professor Reimer Kuehn (King's College London)

Title: Spectra of Random Stochastic Matrices and Relaxation in Complex Systems

Abstract:

We compute spectra of large random stochastic matrices, i.e. Markov
matrices defined on random graphs, where each edge (i,j) in a
(sparse)  random graph is given a positive random weight W_ij >0 in
such a fashion that the each column sum of the matrix W is normalized to
one, Σ_i W_ij= 1. We compute spectra of such matrices, both in
the thermodynamic limit, and for very large single instances. The
stucture of the graphs and the distribution of the non-zero weights
W_ij are largely arbitrary,  as long  as the mean  degree remains
finite  in the thermodynamic limit, and the W_ij satisfy a detailed
balance condition. Knowing the spectra of stochastic matrices is
tantamount to knowing the complete spectrum of relaxation times of
stochastic processes described by  them, so  our results  should have
many interesting  applications for the study of relaxation in  complex
systems. We discuss cell-signalling as a possible application of random
walks in complex networks, and in particular signalling entropy
(constructed in terms of Markov transition matrices) as a global measure
of robustness of networks of signalling pathways.

Colloquium coordinators are Prof.dr. M. Aiello (e-mail : M.Aiello rug.nl ) and
Prof.dr. M. Biehl (e-mail: M.Biehl rug.nl )

http://www.rug.nl/research/jbi/news/colloquia/computerscience