LAPSO IM: A learning based influence maximization approach for social networks
Abstract Online social networks play a pivotal role in the propagation of information and influence as in the form of word of mouth spreading. Influence maximization (IM) is a fundamental problem to identify a small set of individuals, which have maximal influence spread in the social network. IM problem is unfortunately NP hard. It has been depicted that hill climbing greedy approach gives a good approximation guarantee. However, it is inefficient to run a greedy approach on large scale social networks. In this paper, a local influence evaluation function is presented for optimizing IM problem. The local influence evaluation function provides a reliable expected diffusion value of influence spread under the linear threshold, independent and weighted cascade models. To optimize local influence evaluation function, a learning automata based discrete particle swarm optimization (LAPSO IM) algorithm is proposed. LAPSO IM redefines the update rule of particle's velocity based on learning automata action to overcome the weakness of premature convergence. The experimental results on six real world social networks show that the proposed algorithm is more effective than base algorithm DPSO with same the level of efficiency and more time efficient than IMLA with approximate influence spread.
Appl. Soft Comput.