Optimally Starting and Spreading Rumors in Social Networks

Nov 4, 2009

The Target Set Selection problem asks which $k$ people in a network should start an information cascade (e.g. spreading a rumor) so that the expected size of the cascade is as large as possible. For many interesting models of information spread, determining an optimal target set of size k is NP-hard. Kempe, Kleinberg, and Tardos proved that the greedy algorithm provides a $(1 - 1/e - \epsilon)$ approximation to the target set selection problem using submodularity. Rather than target nodes with pieces of information, what happens if we can add edges (make introductions) in the network to create new information pathways? The Introduction Selection problem asks which $k$ edges should be added to a network in order to maximize the spread of a message. This talk surveys the methods of Kempe et al. for the target set selection problem. We present our results for the introduction selection problem using similar techniques. We also discuss some of the limitations of using greedy methods in practice and suggest several directions for future research.