Artificial Intelligence

Spectral Ranking

Thursday, January 11, 2018, 11:00am - 12:00pm PDTiCal
1016 (10th floor class room on eastside)
This event is open to the public.
AI Seminar
Sebastiano Vigna, Università degli Studi di Milano

We sketch the history of spectral ranking—a general umbrella name for techniques that apply the theory of linear maps (in particular, eigenvalues and eigenvectors) to matrices that do not represent geometric transformations, but rather some kind of relationship between entities. Albeit recently made famous by the ample press coverage of Google's PageRank algorithm, spectral ranking was devised more than 100 years ago, and has been studied in game theory, psychology, social sciences, bibliometrics, economy, and choice theory. We describe the contribution given by previous scholars in precise and modern mathematical terms: Along the way, we show how to express in a general way damped rankings, such as Katz's index, as dominant eigenvectors of perturbed matrices, and then use results on the Drazin inverse to go back to the dominant eigenvectors by a limit process. The result suggests a regularized definition of spectral ranking that yields for a general matrix a unique vector depending on a boundary condition.


Sebastiano Vigna's research focuses on 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, pseudorandom number generation, theoretical/experimental analysis of spectral rankings such as PageRank, and axiomatization of centrality measures, 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 first computation of the distance distribution of the whole Facebook graph, from which it was possible to evince that on Facebook there are just 3.74 degrees of separation. Recently, he participated to the analysis of the largest available public web crawl (Common Crawl 2012), which led to the publication of the first open ranking of web sites ( His work on Elias-Fano coding and quasi-succinct indices is at the basis of the code of Facebook's "folly" library ( He also collaborated to the first open ranking of Wikipedia pages (, which is based on his body of work on centrality in networks. His pseudorandom number generator xorshift128+ is the current stock generator of Google's V8 JavaScript engine, used by Chrome, Safari, Firefox, Edge, and Node.js; it is also the stock generator of the Erlang language.
Sebastiano Vigna obtained his PhD in Computer Science from the Università degli Studi di Milano, where he is currently a Full Professor.

« Return to Events