Influential Nodes in a Diffusion Model for Social Networks

Influential Nodes in a Diffusion Model for Social Networks

| David Kempe¹*, Jon Kleinberg²**, and Éva Tardos²***
This paper presents a model for influence propagation in social networks called the decreasing cascade model. The goal is to maximize the expected spread of an innovation or behavior within a network by selecting a set of individuals to initially activate. The authors show that a greedy algorithm can approximate this goal with a (1 - 1/e - ε) approximation guarantee. The decreasing cascade model generalizes previous models and assumes that the probability of a node influencing another decreases as more attempts are made. The model is analyzed to show that the expected number of influenced nodes is a monotone and submodular function of the targeted set. This allows the application of a well-known theorem by Nemhauser, Wolsey, and Fisher, which guarantees that the greedy algorithm achieves a (1 - 1/e) approximation for maximizing submodular functions. The paper also introduces a general threshold model, which is equivalent to the decreasing cascade model. This model allows for a reparametrization of the probability space and provides a way to analyze the influence process. The authors show that the decreasing cascade model is more general than previous models and that the techniques used to prove submodularity in earlier models do not apply here. The paper concludes by discussing the implications of these results for future research, including the investigation of more general influence models and the evaluation of the function σ(A), which measures the expected size of the final active set. The results demonstrate that the greedy algorithm is effective in approximating the optimal solution for the influence maximization problem in the decreasing cascade model.This paper presents a model for influence propagation in social networks called the decreasing cascade model. The goal is to maximize the expected spread of an innovation or behavior within a network by selecting a set of individuals to initially activate. The authors show that a greedy algorithm can approximate this goal with a (1 - 1/e - ε) approximation guarantee. The decreasing cascade model generalizes previous models and assumes that the probability of a node influencing another decreases as more attempts are made. The model is analyzed to show that the expected number of influenced nodes is a monotone and submodular function of the targeted set. This allows the application of a well-known theorem by Nemhauser, Wolsey, and Fisher, which guarantees that the greedy algorithm achieves a (1 - 1/e) approximation for maximizing submodular functions. The paper also introduces a general threshold model, which is equivalent to the decreasing cascade model. This model allows for a reparametrization of the probability space and provides a way to analyze the influence process. The authors show that the decreasing cascade model is more general than previous models and that the techniques used to prove submodularity in earlier models do not apply here. The paper concludes by discussing the implications of these results for future research, including the investigation of more general influence models and the evaluation of the function σ(A), which measures the expected size of the final active set. The results demonstrate that the greedy algorithm is effective in approximating the optimal solution for the influence maximization problem in the decreasing cascade model.
Reach us at info@study.space
[slides] Influential Nodes in a Diffusion Model for Social Networks | StudySpace