When: Wednesday, November 04, 12:00 p.m.

Where: 6115 Gates & Hillman Centers

Brendan R. Meeder,
Computer Science Department

Speaking Skills Talk

Abstract:
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 results for optimizing sub-modular set functions. 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.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

<< Back