Georgia Institute of Technology College of Sciences

Real life networks are usually large and have a very complicated structure. It is tempting therefore to simplify or reduce the associated graph of interactions in a network while maintaining its basic structure as well as some characteristic(s) of the original graph. A key question is which characteristic(s) to conserve while reducing a graph. Studies of dynamical networks reveal that an important characteristic of a network's structure is a spectrum of its adjacency matrix. In this talk we present an approach which allows for the reduction of a general weighted graph in such a way that the spectrum of the graph's (weighted) adjacency matrix is maintained up to some finite set that is known in advance. (Here, the possible weights belong to the set of complex rational functions, i.e. to a very general class of weights). A graph can be isospectrally reduced to a graph on any subset of its nodes, which could be an important property for various applications. It is also possible to introduce a new equivalence relation in the set of all networks. Namely, two networks are spectrally equivalent if each of them can be isospectrally reduced onto one and the same (smaller) graph. This result should also be useful for analysis of real networks. As the first application of the isospectral graph reduction we considered a problem of estimation of spectra of matrices. It happens that our procedure allows for improvements of the estimates obtained by all three classical methods given by Gershgorin, Brauer and Brualdi. (Joint work with B.Webb) A talk will be readily accessible to undergraduates familiar with matrices and complex functions.