Everything you always wanted to know about graph centrality (but were afraid to ask), or: why PageRank never really worked

Date: 
Wednesday, April 11, 2012 - 10:27am

UCSB COMPUTER SCIENCE DEPARTMENT PRESENTS:

Wednesday, May 2, 2012
3:30 – 4:30 PM
Computer Science Conference Room, Harold Frank Hall Rm. 1132

HOST: Giovanni Vigna

SPEAKER: Sebastiano Vigna
Associate Professsor, Università degli Studi di Milano

Title: Everything you always wanted to know about graph centrality (but
were afraid to ask), or: why PageRank never really worked

Abstract:

Starting in the late ’40s, sociologists and psychologists have
investigated the notion of centrality in groups of people linked by some
kind of friendship or endorsement relation (e.g., which people are more
important, or more apt to become a leader). Centrality is also a central
subject in the evaluation of sport teams, citation data, and, more
recently, in the field of information retrieval: the web has become the
main subject of study, and the ample, inaccurate press coverage of
PageRank has pushed centrality back to the center of the stage. In this
talk I will present unpublished work in collaboration with Paolo Boldi
which tries to answer the following question: do we really know whether
all these centrality indices work as touted? We propose three different
objective evaluation strategies, which yield consistent and quite
surprising results.

Bio:

Sebastiano Vigna obtained his PhD in Computer Science from the
Università degli Studi di Milano, where he is currently an Associate
Professor. His interests lie in the interaction between theory and
practice. He has worked on highly theoretical topics such as
computability on the reals, distributed computability,
self-stabilization, minimal perfect hashing, succinct data structures,
query recommendation, algorithms for large graphs and
theoretical/experimental analysis of spectral rankings such as PageRank,
but he is also (co)author of several widely used software tools ranging
from high-performance Java libraries to a model-driven software
generator, a search engine, a crawler, a text editor and a graph
compression framework. In 2011 he collaborated to the computation of the
distance distribution of the whole Facebook graph, from which it was
possible to evince that there on Facebook there are just 3.74 degrees of
separation.