University of Rome, La Sapienza
4pm Monday, 15th November, 2010
Room G.03, Informatics Forum
The coming-together of large scale social networks and the Internet via artifacts such as the World Wide Web, social networking sites like Facebook, services like Email, chats and so on, is having a profound impact within and beyond computer science.Key web services like search, recommendation systems and computational advertising are based on the study, both theoretical and empirical, of huge social networks of various types. For the social sciences the consequences are probably deep and lasting. For the first time in human history we can observe and measure various social phenomena on a very large scale. On social networking sites we can observe the birth of friendships, the dynamics of trust, how fads and ideas spread and fade away.
In this surveyish talk I will give a few examples of contemporary algorithmic research in this context drawn from my own experience. Specifically, the results described, obtained in collaboration with several colleagues, will concern new, low-entropy models for the web graph, compression algorithms for social networks, and an almost tight upper bound on the speed with which rumours spread across a social network.