The Algorithmics of Information Diffusion in Social Networks
Lecturer:
Professor Alessandro Panconesi
(Roma Sapienza, Italy).
About the lecturer | Course Summary | Slides | Assignment
About the lecturer:
Alessandro Panconesi is full professor of Computer Science at Sapienza, University of Rome. He recieved a PhD in Computer Science from Cornell University in 1993. He is the recipient of several awards such as the ACM Danny Lewin Award, an IBM Faculty Award, two Yahoo! Research Awards and two Google Research Faculty Awards. His main research interests are in the area of distributed and randomized algorithms and, more recently, the algorithmics of social networks and the web.
Course summary: Computer Science is no more about computers than astronomy is about telescopes, quipped the great late computer scientist Edsger W. Dijkstra. Telescopes and computers can indeed be more related that one might think. As telescopes are used to scrutinize and unravel the mysteries of the skyes, the Internet is a giant make-shift observatory of human kind. Thanks to the internet, for the first time in the history of science, we can gather and analyze huge amounts of data that are the shadows of human social behaviour. Can this revolutionize the social sciences?
In this brief course we will discuss a few paradigmatic examples taken from this larger context. In particular we will focus on information diffusion (epidemic) processes in social networks chosen to exemplify the fascinating interplay between theory and experiments that is typical of this exciting area of research, seen from the point of view of algorithmic research.
Slides:- Part 1: Milgram's small world experiment
- Part 2: Chain letters
- Part 3: Rumour spreading in social networks
- Part 4: Rumour spreading without the network
- The small world problem by S. Milgram (1967)
- An experimental study of the small world problem by J. Travers and S. Milgram (1969)
- Collective dynamics of 'small-world' networks by D. J. Watts and S. H. Strogatz (1998)
- The small-world phenomenon: an algorithmic perspective by J. Kleinberg (2000)
- Reconstructing patterns of information diffusion from incomplete observations by F. Chierichetti, J. Kleinberg and D. Liben-Nowell (2011)
- Rumour spreading and graph conductance by F. Chierichetti, S. Lattanzi and A. Panconesi (2011)
- Network coding: an introduction by T. Ho and D. S. Lun
- Analyzing network coding gossip made easy by B. Haeupler (2011)
You can find the problem set here. Please send your solutions (or questions, should you have any) to Bartosz Klin by Friday, May 17.