Better approximation algorithms for influence maximization in online social networks

Better approximation algorithms for influence maximization in online social networks

0.00 Avg rating0 Votes
Article ID: iaor201526109
Volume: 30
Issue: 1
Start Page Number: 97
End Page Number: 108
Publication Date: Jul 2015
Journal: Journal of Combinatorial Optimization
Authors: , , , , ,
Keywords: networks, internet
Abstract:

Influence maximization is a classic and hot topic in social networks. In this paper, firstly we argue that in online social networks, due to the time sensitivity of popular topics, the assumption in IC or LT model that the influence propagates endlessly in the network, is not applicable. Based on this we consider influence transitivity and limited propagation distance in our new model. Secondly, under our model we propose Semidefinite based algorithms. While most existing algorithms rely on monotony and submodularity to obtain approximation ratio of 1 1 / e equ1 , when no size limitation exists on the number of seeds, our algorithm achieves approximation ratio with 0.857 equ2 , which is a great improvement. Moreover, when only a limited number of nodes can be chosen as seeds, based on computer‐assisted proof, we claim our algorithm still keeps approximation ratio higher than 1 1 / e equ3 if the ratio of the seeds to the total number of nodes resides in a certain range. At last, we evaluate the effectiveness of our algorithms through extensive experiments on real world social networks.

Reviews

Required fields are marked *. Your email address will not be published.