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(theta(nu) and b(u nu)) 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.