Combining intensification and diversification to maximize the propagation of social influence

Abstract

In this paper we consider the influence maximization problem in social networks, and propose an Int-Div heuristic to solve it. Motivated by the concepts of intensification and diversification in optimization problems, Int-Div accounts for both of these two concepts to estimate the social influence, and selects nodes based on marginal influence increment. It is applicable to the two widely used diffusion models, namely, the Linear Threshold Model and the Independent Cascade Model. The proposed strategy is evaluated through experiments on a collaboration network and a who-trust-whom online social network, respectively, and compared with several existing heuristics, namely, the pure greedy algorithm, the centrality-based scheme, the single discount and the degree discount heuristics. We find that our proposed strategy offers better performance than the centrality-based scheme, the single discount and the degree discount heuristics, while achieving approximately the same performance as the greedy algorithm. The computational load is dramatically lower than the greedy heuristic.