Event Details

Event Details:

Is getting a new follower on Twitter advantageous? And what about about getting a new friend on Facebook? We discuss problems of score and rank monotonicity for spectral ranking methods, such as eigenvector centrality and PageRank, in directed and undirected graphs. Score monotonicity means that adding an arc increases the score at the end of the arc. Rank monotonicity means that after adding an arc towards x nodes with a score lower than x retain this property. In the undirected case, this must be true for both endpoints of an edge. We show that common spectral rankings are both score and rank monotone on directed, strongly connected graphs, but also that, surprisingly, the situation is very different for undirected graphs, and in particular that PageRank is neither score nor rank monotone. To obtain results for every value of the damping factor, we resort to graph fibrations, which make it possible to prove analytical properties of infinite families of counterexamples.

Host: Deborah Khider, POC: Maura Covaci

YOU ONLY NEED TO REGISTER ONCE TO ATTEND THE ENTIRE SERIES – We will send you email announcements with details of the upcoming speakers.

Register in advance for this webinar: https://usc.zoom.us/webinar/register/WN__0VhakI6Q6i3JsasdmNWcA.

After registering, you will receive an email confirmation containing information about joining the Zoom webinar.

The recording for this Interview Seminar talk will be posted on our USC/ISI YouTube page: https://www.youtube.com/user/USCISI.

Speaker Bio

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. 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.