Photo by GuerrillaBuzz on UnsplashAbstract
Understanding the correlation between two different scores for the same set of items is a common problem in graph analysis and information retrieval. The most commonly used statistics that quantifies this correlation is Kendall’s $ au$; however, the standard definition fails to capture that discordances between items with high rank are more important than those between items with low rank. Recently, a new measure of correlation based on average precision has been proposed to solve this problem, but like many alternative proposals in the literature it assumes that there are no ties in the scores. This is a major deficiency in a number of contexts, and in particular when comparing centrality scores on large graphs, as the obvious baseline, indegree, has a very large number of ties in social networks and web graphs. We propose to extend Kendall’s definition in a natural way to take into account weights in the presence of ties. We prove a number of interesting mathematical properties of our generalization and describe an $O(n log n)$ algorithm for its computation. We also validate the usefulness of our weighted measure of correlation using experimental data on social networks and web graphs.
Recording of the Talk (RMIT Account Required)
Getting There
Sebastiano Vigna
Professor at the Università degli Studi di Milano
Sebastiano Vigna’s research focuses on the interaction between theory and practice. He has worked on 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.
Chenglong Ma
Research Fellow
I’m a Research Fellow at ADM+S RMIT node. My research interests include Information Retrieval, Recommender Systems, and Responsible AI.