Brendan is a 2nd year PhD student at Carnegie Mellon University in Pittsburgh, PA USA. At CMU he studies social networks through a theoretical and empirical lens with his advisors Luis von Ahn and Manuel Blum. He is interested in theory and enjoys daydreaming about math. You've probably seen him floating around D1 this summer.

AG 1, SWS   Info

AG Audience

English

30 Minutes

Saarbrücken

With the growth of social networks it has become feasible to market a product using few resources. The success of such a scheme depends on word of mouth spreading. One interesting question to ask is the following: If you have k samples of a product and a model of how individuals will talk to each other, to which k people should you give the samples? This is the target set selection problem. It is also interesting to ask how creating introductions in the network can improve the flow of information. We call this problem the introduction selection problem.

In general these combinatorial optimization problems are computationally hard, but by exploiting the property of submodularity a simple greedy algorithm gives a (1 - 1/e) factor approximation. In this talk I will explain several proposed models for information propagation in networks. I will present some results of Kempe, Kleinberg, and Tardos for the target set selection problem, as well as some results for the introduction selection problem.

Ariel Rebecca Levavi

--email hidden

passcode not visible

logged in users only

Social Networks; Rumor Spreading