Artificial Intelligence

The Case for Kendall's Assortativity

When:
Wednesday, January 08, 2020, 11:00am - 12:00pm PSTiCal
Where:
689 6th floor conference room
This event is open to the public.
Type:
AI Seminar
Speaker:
Prof. Sebastiano Vigna (University of Milan)
Video:
https://bluejeans.com/s/TD0pN/
Description:

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