### DYNAMICAL NETWORKS, ISOSPECTRAL GRAPH REDUCTION

- Series
- School of Mathematics Colloquium
- Time
- Thursday, November 5, 2009 - 11:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 269
- Speaker
- Lyonia Bunimovich – Georgia Tech

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.