Artificial Intelligence

The Case for Kendall's Assortativity

Wednesday, January 08, 2020, 11:00am - 12:00pm PDTiCal
689 6th floor conference room
This event is open to the public.
AI Seminar
Prof. Sebastiano Vigna (University of Milan)

Since the seminal work of Litvak and van der Hofstad, it has been known that Newman’s assortativity, being based on Pearson’s correlation, is subject to a pernicious size effect which makes large networks with heavy-tailed degree distributions always unassortative. Usage of Spearman’s ρ, or even Kendall’s τ was suggested as a replacement but the treatment of ties was problematic for both measures. In this paper we first argue analytically that the tie-aware version of τ solves the problems observed, and we show that Newman’s assortativity is heavily influenced by tightly knit communities. Then, we perform for the first time a set of large-scale computational experiments on a variety of networks, comparing assortativity based on Kendall’s τ and assortativity based on Pearson’s correlation, showing that the pernicious effect of size is indeed very strong on real-world large networks, whereas the tie-aware Kendall’s τ can be a practical, principled alternative.

Sebastiano Vigna is a professor of computer science at the University of Milan. He created the xorshift+ and xoroshiro128+pseudorandom number generators. Xorshift128+ is used in the javascript engines of ChromeFirefox, and Safari. In 1991, he received a laurea in Mathematics and in 1996 a Ph.D. in computer science; both from the University of Milan. He developed UbiCrawler, a web crawler, in a collaboration with others. Is recent work is in compression, analysis and understanding of web and social graphs and knowledge bases. 

« Return to Events