This paper presents a study on maximizing the spread of influence through social networks. The authors consider the problem of selecting a subset of individuals to target in order to trigger a large cascade of further adoptions of a new product or innovation. They analyze this problem in several widely studied models of social network analysis, and show that the optimization problem of selecting the most influential nodes is NP-hard. They provide the first provable approximation guarantees for efficient algorithms, showing that a natural greedy strategy achieves a solution that is provably within 63% of optimal for several classes of models. The authors also provide computational experiments on large collaboration networks, showing that their approximation algorithms significantly outperform node-selection heuristics based on degree centrality and distance centrality. They consider two basic diffusion models: the Linear Threshold Model and the Independent Cascade Model. In both models, they show that the resulting influence function is submodular, and that a greedy hill-climbing algorithm can be used to approximate the optimal solution to within a factor of (1 - 1/e - ε), where e is the base of the natural logarithm and ε is any positive real number. The authors also show that the influence maximization problem is NP-hard for both the Linear Threshold and Independent Cascade models. They propose a general framework that simultaneously includes both of these models as special cases, and show how to obtain approximation guarantees for a large sub-class of these models. They also consider extensions of their approximation algorithms to models with more realistic scenarios, including more complex marketing actions and non-progressive processes. The authors conclude that their results provide a general approach for reasoning about the performance guarantees of algorithms for influence problems in social networks. They also show that their approximation algorithms significantly outperform node-selection heuristics based on degree and distance centrality in computational experiments on large collaboration networks.This paper presents a study on maximizing the spread of influence through social networks. The authors consider the problem of selecting a subset of individuals to target in order to trigger a large cascade of further adoptions of a new product or innovation. They analyze this problem in several widely studied models of social network analysis, and show that the optimization problem of selecting the most influential nodes is NP-hard. They provide the first provable approximation guarantees for efficient algorithms, showing that a natural greedy strategy achieves a solution that is provably within 63% of optimal for several classes of models. The authors also provide computational experiments on large collaboration networks, showing that their approximation algorithms significantly outperform node-selection heuristics based on degree centrality and distance centrality. They consider two basic diffusion models: the Linear Threshold Model and the Independent Cascade Model. In both models, they show that the resulting influence function is submodular, and that a greedy hill-climbing algorithm can be used to approximate the optimal solution to within a factor of (1 - 1/e - ε), where e is the base of the natural logarithm and ε is any positive real number. The authors also show that the influence maximization problem is NP-hard for both the Linear Threshold and Independent Cascade models. They propose a general framework that simultaneously includes both of these models as special cases, and show how to obtain approximation guarantees for a large sub-class of these models. They also consider extensions of their approximation algorithms to models with more realistic scenarios, including more complex marketing actions and non-progressive processes. The authors conclude that their results provide a general approach for reasoning about the performance guarantees of algorithms for influence problems in social networks. They also show that their approximation algorithms significantly outperform node-selection heuristics based on degree and distance centrality in computational experiments on large collaboration networks.