Structural analysis of complex networks: from local measurements to eigenvalues

Friday, March 2, 2012 - 11:30am - 12:00pm
Keller 3-180
Victor Preciado (University of Pennsylvania)
The intricate structure of many large-scale networked
systems has attracted the attention of the scientific
community, leading to many results attempting to explain
the relationship between the structure of the network and node dynamics.
A common approach to study the structure is to use synthetic network models in which structural properties of interest, such as degree distributions,
are prescribed. Although very common, this approach can have a major flaw: Synthetic network models implicitly induce many structural properties that are not directly controlled and can be relevant to the network performance. Therefore, it is difficult to draw conclusions about the role of a particular structural property in a real network using synthetic models. In this
talk, I will present an alternative view where instead of prescribed random models, I use algebraic graph theory and convex optimization to study how structural properties constrain those global network invariants that effects dynamics and performance(e.g. eigenvalues of adjacency and Laplacian matrices). Using examples such as dynamics of epidemic spreading on large social networks and synchronization on the power grid as examples, I will discuss examples we will see when macroscopic local measurements such as degree distributions and clustering constrain the eigenvalues and when they do not.

joint work with Victor Preciado
MSC Code: