Scalable influence maximization in social networks

Abstract

Influence maximization is the problem of selecting a subset of individuals in a social network such that they maximize the spread of an influence. It is desirable to generate an idea diffusion cascade by making these initial influencers adopt it first. In other words, using the word-of-mouth "power" of these initial individuals should allow us to maximize the spread of an idea over the network. The problem of finding the most influential nodes in a network is NP-hard. Kempe, Kleinberg, and Tardos (2003) has proved that a Greedy algorithm strategy obtains a solution that is provably within 63% of optimal for several cases; However it is computationally prohibitive to run this algorithm in large social networks. Finding scalable solutions for this problem is critical for enabling applications in viral social marketing among other topics like detection sensor location or trend monitoring. In this thesis, a new heuristic algorithm is presented for mining top-K influencers based on a local influence region probability spread score. The proposed algorithm is composed of: 1) a bounded variation of breadth-first search traversal algorithm for calculating the mentioned score of each individual; and 2) an iterative greedy select-and-update algorithm for choosing top influencers. Experiment results show that this new algorithm can in several cases perform better (in influence spread and computational efficiency) than previous Works.