Large Graphs and Networks: Matrix Algorithms and Applications
Tuesday September 11, 2007

The Manchester Institute for Mathematical Sciences (MIMS) is hosting this workshop in our new facilities in the Alan Turing Building. This is an informal afternoon workshop covering new developments in matrix-based algorithms for large graphs and networks. The two external speakers will treat applications to biological networks and the Google search engine. Professor Ipsen is visiting MIMS from 10 September 2007 - 21 September 2007.

In order to register for the workshop please email Sebastian Rees. There is no registration charge.

Location

The workshop takes place in the Frank Adams Room (1.212) in MIMS in the Alan Turing Building

Programme

2.00pm-3.00pm - Des Higham (University of Strathclyde).

"Spectral Algorithms for Biological Networks"

Abstract (click to view)

Advances in experimental biology are creating challenging modelling and data analysis problems. In particular, protein-protein interaction data sets can be viewed as large unweighted, undirected graphs that, when analyzed appropriately, may reveal important biological information. Researchers have considered high-level questions, such as "can we describe these networks in terms of a few parameters?'' and low-level questions such as "can we identify interesting groups of proteins?''. I will describe two graph models, geometric and lock-and-key, that aim to contribute at both levels. These models naturally give rise to computational algorithms. Results for real biological data sets will be given.

3.00pm-3.30pm

Refreshments

3.30pm-4.30pm - Ilse Ipsen (North Carolina State University)

"The Mathematics Behind Google's PageRank"

Abstract (click to view)

How does the search engine Google decide in which order to display the web pages that result from a search? A major ingredient in this decision is PageRank, which is a score associated with every web page. Increasing the PageRank of a company's web page has become an important factor in many marketing strategies. PageRank only depends on the links among web pages, but not on their content. Mathematically, PageRank can be viewed as the stationary distribution of a stochastic matrix whose dimension is now in the hundreds of billions. Hence the computation of PageRank if often referred to as the world's largest matrix computation. We discuss the mathematical problem behind PageRank, its numerical computation, as well as efficient criteria that can guarantee correct ranking of the PageRank scores. A round off error analysis demonstrates the validity of the ranking criteria for matrices with dimension up to 10^(14), and numerical experiments illustrate that our criteria can effectively rank the top PageRank scores.

Other Information

The organizer is Nick Higham

Financial support for the workshop comes from the Royal Society and the Wolfson Foundation.