Journal
JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 30, Issue 1, Pages 97-108Publisher
SPRINGER
DOI: 10.1007/s10878-013-9635-7
Keywords
Influence maximization; Semidefinite programming; Approximation algorithm
Funding
- U.S. National Science Foundation [CNS-0831579, CNS-1016320, CCF-0829993]
- National Natural Science Foundation of China [11001242, 11071220]
Ask authors/readers for more resources
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 , when no size limitation exists on the number of seeds, our algorithm achieves approximation ratio with , 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 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available