Abstract

The spread of information, memes, and news through social networks is becoming pivotal for society today. Significant resources are being invested in online marketing, which thanks to the growth of online social networks can now potentially target hundreds of millions of people. Still, our knowledge of the basic mechanisms governing the spread of information is very limited. In this talk, we will discuss some of the work we have been doing in this area.

First, we will present a result that allows us to express the time needed for information to spread in terms of a network parameter known as conductance. Our result here can be viewed as providing a way to quantify the effect of Granovetter’s “weak ties” in facilitating the diffusion of information. Second, we will consider the related problem of inferring properties of a social network using a limited set of information traces that traversed it. We will show some theoretical results, together with the predictions they entail on a chain-letter data set that circulated extensively in the last decade.

(Joint work with Silvio Lattanzi and Alessandro Panconesi, and with David Liben-Nowell and Jon Kleinberg.)