Title: Maximizing the spread of in uence through a social network

Authors: D. Kempe, J. Kleinberg, and E. Tardos


Models for the processes by which ideas and influence propagate through a social network have been studied in a number of do- mains, including the diffusion of medical and technological innova- tions, 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 fun- damental 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 influential nodes is NP-hard here, and we pro- vide the first provable approximation guarantees for efficient algo- rithms. Using an analysis framework based on submodular func- tions, 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 influence problems in social networks. We also provide computational experiments on large collabora- tion networks, showing that in addition to their provable guaran- tees, our approximation algorithms significantly out-perform node- selection heuristics based on the well-studied notions of degree centrality and distance centrality from the field of social networks.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale