Abstract
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 a century ago, and has been studied in tournament ranking, 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.
About the Speaker
Sebastiano Vigna is a Professor the University of Milan. His 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. 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. His work on the Elias-Fano encoding and quasi-succinct indices is at the basis of the code of Facebook's "folly" library. His pseudorandom number generator xorshift128+ is the current stock generator of Google's V8 JavaScript engine, and it is used by Chrome, Safari, Firefox, Edge, and Node.js; it is also the stock generator of the Erlang language. His pseudorandom number generators xoroshiro128++ and xoshiro256++ (co-designed with David Blackman) are part of the new random package of Java 17, together with LXM, a new family of generators designed in collaboration with Guy Steele.