Navigation and Evolution of Social Networks
David Liben-Nowell, Carleton College

Slides

Imagine yourself in Ancient Greece, newly crowned as a chariot-racing champion, when you are accidentally stabbed by the laurel wreath with which your achievement is being marked. But is laurel poisonous? What is the antidote? 2400 years before the invention of the web, you would have to seek this information from your friends and, indirectly, their friends, their friends' friends, and so on. Social networks are formal structures that encode these connections between people, and the recent explosion of online data recording social interactions has granted us the opportunity to analyze these networks with the full power of algorithmic graph theory. In this tutorial, I will introduce some of the empirical observations of the structure of social networks, especially in comparison to the structure of the web. We will then discuss a number of algorithmic topics arising in social networks, including the latent information contained in social networks (how much information about people is implicit in their connections?) and how to search social networks (can you find a short path to a target without global knowledge of the graph?).