| David Kempe1*, Jon Kleinberg2**, and Éva Tardos2***
This paper by David Kempe, Jon Kleinberg, and Éva Tardos explores the problem of maximizing the spread of an innovation or behavior within a social network through word-of-mouth referrals. The authors introduce a general model called the *decreasing cascade model*, which generalizes models used in sociology and economics. In this model, a behavior spreads in a cascading fashion, starting with a set of initially "active" nodes. The goal is to select a set of individuals to target for initial activation to maximize the expected size of the final active set.
The paper presents a greedy algorithm that selects nodes based on their marginal gain in activating other nodes. The algorithm is shown to be a $(1-1/e)$-approximation for selecting a set of size $k$. The proof of this result relies on demonstrating that the expected number of influenced nodes is a monotone and submodular function of the targeted set. The authors also introduce a generalized version of Granovetter's threshold model to reparametrize the probability space, allowing for a more detailed analysis of the dynamics of the process.
The paper concludes with a discussion on the limitations of previous techniques and future directions, including the need to investigate more general influence models and the evaluation of the function that measures the expected number of influenced nodes.This paper by David Kempe, Jon Kleinberg, and Éva Tardos explores the problem of maximizing the spread of an innovation or behavior within a social network through word-of-mouth referrals. The authors introduce a general model called the *decreasing cascade model*, which generalizes models used in sociology and economics. In this model, a behavior spreads in a cascading fashion, starting with a set of initially "active" nodes. The goal is to select a set of individuals to target for initial activation to maximize the expected size of the final active set.
The paper presents a greedy algorithm that selects nodes based on their marginal gain in activating other nodes. The algorithm is shown to be a $(1-1/e)$-approximation for selecting a set of size $k$. The proof of this result relies on demonstrating that the expected number of influenced nodes is a monotone and submodular function of the targeted set. The authors also introduce a generalized version of Granovetter's threshold model to reparametrize the probability space, allowing for a more detailed analysis of the dynamics of the process.
The paper concludes with a discussion on the limitations of previous techniques and future directions, including the need to investigate more general influence models and the evaluation of the function that measures the expected number of influenced nodes.