University of Twente

Kevin McCurley (Google)

Remco van der Hofstad (TU/e)

TIME: Friday April 24, 9.30-11.15

LOCATION: Citadel T300, see campus map at http://www.utwente.nl/contact/contact.doc/

9.30-10.15 Kevin McCurley. Information modeling with graphs.

10.15-10.30 Coffee, tea

10.30-11.15 Remco van der Hofstad. Random graphs with an exponential weight structure.

13.00 PhD defense by Yana Volkovich. Thesis: `Stochastic Analysis of Web Page Ranking'

The abstracts and short bio of the speakers are below.

TITLE: Information Modeling with Graphs

ABSTRACT: The founders of Google started with a relatively simple idea, namely to use a model of human interaction on the World Wide Web and derive a static ranking on documents. When combined with many other signals, this ranking has proved to be remarkably effective for improving the quality of search on the Web.

The underlying mathematics of PageRank involves the stationary distribution of a random walk on an extension of the Web graph. There are numerous variations on the original model, and many mathematical questions that arise from the characteristics of such models. In this talk I will describe yet another class of graphical models for information on the web, motivated by the problem of finding "similar documents".

SHORT BIO: Kevin McCurley is a research scientist at Google in California, working in the research group. He received his PhD in mathematics in 1981 from the University of Illinois. Prior to joining Google in 2005, he held positions at Michigan State University, University of Southern California, Sandia National Laboratories, and IBM Research. He has interests in several fields, including number theory, algorithms, cryptography, economics, and web research.

TITLE:

Random graphs with an exponential weight structure

ABSTRACT:

We study the structure of minimal-weight paths in the configuration model with i.i.d. degrees with a fixed degree distribution. Here, each edge receives an independent exponential weight, and we consider hopcount, which equals the number of edges of the minimal-weight path between two uniformly chosen vertices, and the weight of this minimal path.

When the degrees obey a power law with degree power-law exponent \tau, then, whenever \tau>2, we see that the hopcount obeys a central limit theorem with asymptotically equal mean and variance proportional to \log{n}, where n is the size of the graph.

A similar result was proved to hold on the complete graph, the difference being that the proportionality constant on the complete graph is equal to 1, whereas for the configuration model it is greater than 1 when \tau>3 and in (0,1) when \tau\in (2,3). This gives a remarkably

universal picture for first passage percolation on random graphs. Peculiarly, when \tau\in (1,2), for which the mean degree is infinite, the hopcount weakly converges to a rather explicit distribution in terms of the Poisson-Dirichlet distribution.

These results should be contrasted to the results when instead of i.i.d. exponential weights, each edge has a constant weight, so that the hopcount is equal to the graph distance on the graph. In the latter case, when \tau\in (2,3), the hopcount is asymptotically proportional to \log\log{n}, with uniformly bounded fluctuations. Thus, the addition of random edge weights has a marked effect on the structure of minimal-weight paths. We hope that these results shed light on the hopcount in Internet, which also obeys an asymptotic central limit theorem with roughly equal mean and variance.

SHORT BIO:

Remco van der Hofstad received his PhD at the University of Utrecht in 1997, under the supervision of Frank den Hollander and Richard Gill. Since then, he worked at McMaster University in Hamilton, Canada, and Delft University of Technology.

He is currently full professor in probability at Eindhoven University of Technology. Further, he is jointly with Frank den Hollander responsible for the `Random Spatial Structures' Program at EURANDOM.

Remco received the Prix Henri Poincare 2003 jointly with Gordon Slade, the Rollo Davidson Prize 2007, and is a laureate of the `Innovative Research VIDI Scheme' 2003 and `Innovative Research VICI Scheme' 2008.