Informatics Seminar on Wednesday, June 10th, 15.30 - Prof. Paolo Boldi
Staff - Faculty of Informatics
Start date: 10 June 2009
End date: 11 June 2009
The Faculty of Informatics is pleased to announce a seminar given by Prof. Paolo Boldi
TITLE: Functional dependencies of PageRank
SPEAKER: Prof. Paolo Boldi, Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano
DATE: June 10th , 2009
PLACE: USI Università della Svizzera italiana, room SI-008, 'Informatics Building' (Via G. Buffi 13)
TIME: 15.30
ABSTRACT:
PageRank is defined as the stationary state of a Markov chain, obtained by perturbing the transition matrix induced by a web graph with a damping factor $\alpha$ that spreads part of the rank in a uniform way. The choice of $\alpha$ is eminently empirical, and in most cases the original suggestion $\alpha=0.85$ by Brin and Page is still used.
In this talk, we give a mathematical analysis of PageRank when $\alpha$ changes. In particular, we show that, contrarily to popular belief, for real-world graphs values of $\alpha$ close to $ do not give a meaningful ranking. We also give closed-form formulae for PageRank derivatives of any order, and we show how to approximate them in practice. Finally, we view PageRank as a linear operator acting on the preference vector and show a tight connection between iterated computation and derivation.
BIO:
Paolo Boldi obtained his Ph.D. in Computer Science at the University of Milano, where he is currently Associate Professor at the Dipartimento di Scienze dell'Informazione. His research interests touched many different topics in theoretical and applied computer science, such as: domain theory, semantics of parallel and distributed systems, non-classical computability theory (type-2 Turing machines and Blum-Shub-Smale model), distributed computability, anonymous and partially anonymous networks, sense of direction, self- stabilizing systems.
More recently, his works focused on problems related to the World-Wide Web, a field where his research has also produced software packages used by many people working in the same area. In particular, he contributed to write a fully distributed fault-tolerant crawler (UbiCrawler),; a highly efficient full-text IR engine (MG4J); a graph compression tool (WebGraph) that is state-of- art as far as compression ratio is concerned; a library of succinct data structures for storing sequences and functions.
On a more theoretical side, he worked on some issues related to PageRank computation and evaluation, on efficient algorithms to store inverted indices for large text collections, on some theoretical and practical aspects related to interval search, on querylog analysis and on the problem of monotone minimal perfect hashing.
HOST: Prof. Fabio Crestani
