Dr Damien Fay, Computer Laboratory, Cambridge
Representing data and networks in the form of graphs has become a hot topic in recent years, especially with the growth of social networking sites, interaction networks between proteins and of course in computer networks. However, there is little material on compressing the information in a graph into a 'useful' set of numbers. The weighted spectral distribution (WSD) presented in this talk is one such transform and is (in the full statistical sense) a graph metric. The metric is based on the distribution of the eigenvalues of the Normalised Laplacian and, as will be demonstrated in the talk with the aid of simple examples, is equivalent to determining where cycles of short lengths occur in a graph.
Once we can measure the distance between graphs, this opens the area of applied graph theory to many techniques from classical statistics. I will demonstrate several of those techniques in this talk using clear examples:
1. How to estimate the best parameters of a topology generator given a target topology? Or, put another way, which of the competing 'Internet topology generators' is closest to the measured Internet?
2. How does the Internet (at AS level) evolve over time and what mechanism underlies this evolution?
3. How can we cluster graphs? With the use of Random Projection as one technique and Multi-dimensional scaling as an alternative I will demonstrate some approaches to the following problems:
a. Determining the difference between topology generators.
b. Network application detection from application graph clustering (via the WSD).
c. Can we separate the Protein-Protein interaction graphs of Breast cancer patients? - an ongoing problem.
d. Given an image of a subject can we tell what expression they have on their face?
Biography:
Damien Fay obtained a B.Eng from University College Dublin (1995), an MEng (1997) and PhD (2003) from Dublin City University and worked as a mathematics lecturer at the National University of Ireland, Galway (2003-2007) before joining the NetOS group, Computer Laboratory, Cambridge in 2007 as a research associate. He is currently a visiting researcher in Galway and will be returning to Cambridge to work on Social networks in April 2010. His research interests include applied graph theory, time series analysis and applied statistics.