Title: Discussion of the paper "Maximizing the Spread of Influence through a Social Network", by David Kempe, Jon Kleinberg and Eva Tardos
Speaker: Martin Pal, DIMACS
Date: November 29, 2004 11:30 - 12:50
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The paper is available from http://www-rcf.usc.edu/~dkempe/publications/index.html
They phrase the problem in terms of maximizing the impact of a marketing campaign with a limited budget, but an equally appealing story could be told about a terrorist who can infect a small number of locations, and wants to choose which locations to infect to do as much damage as possible.
One thing that appeals to me is a nice and clean model of influence (or, for us, disease) spreading. The other is that this paper shows that the computational answer to the question of how to maximize the impact of an outbreak is much more clear-cut than to the question of how to minimize it.
Abstract of the paper:
Models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations, the sudden and widespread adoption of various strategies in game-theoretic settings, and the effects of "word of mouth" in the promotion of new products. Recently, motivated by the design of viral marketing strategies, Domingos and Richardson posed a fundamental algorithmic problem for such social network processes: if we can try to convince a subset of individuals to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target? We consider this problem in several of the most widely studied models in social network analysis. The optimization problem of selecting the most in influential nodes is NP-hard here, and we provide the first provable approximation guarantees for efficient algorithms. Using an analysis framework based on submodular functions, we show that a natural greedy strategy obtains a solution that is provably within 63% of optimal for several classes of models; our framework suggests a general approach for reasoning about the performance guarantees of algorithms for these types of in uence problems in social networks. We also provide computational experiments on large collaboration networks, showing that in addition to their provable guarantees, our approximation algorithms significantly out-perform nodeselection heuristics based on the well-studied notions of degree centrality and distance centrality from the field of social networks. approximation algorithms, social networks, viral marketing, diffusion of innovations.