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.
One particularly popular moment associated to the colloquium is the “Master Class” where students have the opportunity to give a short (but well-prepared) presentation of his/her work. Each presentation (10 minutes) is followed by an open discussion with the guest speaker (15 minutes) who gives a detailed feedback. The complete program is provided here.