A Potential-Based Node Selection Strategy for Influence Maximization in a Social Network

摘要

Social network often serves as a medium for the diffusion of ideas or innovations. The problem of influence maximization which was posed by Domingos and Richardson is stated as: if we can try to convince a subset of individuals to adopt a new product and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target in order to achieve a maximized influence? In this work, we proposed a potential-based node selection strategy to solve this problem. Our work is based on the observation that local most-influential node-selection adopted in many works, which is very costly, does not always lead to better result. In particular, we investigate on how to set two parameters(θ_v and b_(uv)) appropriately. We conduct thorough experiments to evaluate effectiveness and efficiency of the proposed algorithm. Experimental results demonstrate that our approximation algorithm significantly outperforms local-optimal greedy strategy.