Thursday 24 May 2012CS Colloquium: Graph Spectra, Information Theory and Complex Networks

Prof. Edwin Hancock - University of York

Harrison LT004 15:00-16:00

This talk will provide an overview of recent work at York on using ideas from the spectral
analysis of graphs to develop random walks algorithms for the analysis of graph-structure.
The work has its routes in structural pattern recognition and problems such as graph
matching and graph clustering. However, recently we have begun to explore how the
work can be extended into the complex network domain and used to define easily computed measures
of network complexity. The talk will commence with a review of graph-spectra and their links
to diffusions on graphs. We will then show how the heat kernel leads to a number of natural
characterisations of graph structure, and in particular the Ihara zeta function which can be used
to gauge the cycle composition of graphs. Finally, we will show links between graph-spectra and the concept of entropy on a graph.
The talk will be illustrated with examples from object recognition and the analysis of protein-protein
interaction networks.

Add to calendar

Add to calendar (.ics)