Since the 60's, sociologists have been interested in how many friendship links you must traverse in average to get from any person in the world to any other one. Milgram's celebrated experiment, involving a few hundred people, concluded that there were six "degrees of separation". More generally, sociologists were interested in the distance distribution of friendship: how many pairs of people are separated by k degrees? We will discuss some new, high-performance diffusion-based approximate algorithms that made it possible to conclude that on Facebook there are 3.74 degrees of separation using commodity hardware, and to analyze how this value decreased in time. The same algorithms can be used to compute on very large graphs centrality measures based on distances, such as closeness and harmonic centrality, which provide interesting, high-quality rankings.
There will be a cocktail at 17:15, .
Sorbonne Université - Faculty of Science & EngineeringCampus Pierre et Marie Curie
4 place Jussieu
75005 Paris (métro Jussieu)
How to reach Sorbonne University (Faculty of Science & Engineering).