Top-K Influential Nodes in Social Networks: A Game Perspective
This addresses the problem of efficiently identifying influential nodes for viral marketing, though it is incremental as it builds on existing models and algorithms.
The paper tackles influence maximization in social networks by introducing a Coordination Game model that generalizes existing models like Majority Vote and Linear Threshold, and shows that their accelerated algorithm significantly outperforms other heuristics and is three orders of magnitude faster than the original greedy method.
Influence maximization, the fundamental of viral marketing, aims to find top-$K$ seed nodes maximizing influence spread under certain spreading models. In this paper, we study influence maximization from a game perspective. We propose a Coordination Game model, in which every individual makes its decision based on the benefit of coordination with its network neighbors, to study information propagation. Our model serves as the generalization of some existing models, such as Majority Vote model and Linear Threshold model. Under the generalized model, we study the hardness of influence maximization and the approximation guarantee of the greedy algorithm. We also combine several strategies to accelerate the algorithm. Experimental results show that after the acceleration, our algorithm significantly outperforms other heuristics, and it is three orders of magnitude faster than the original greedy method.