Better approximation algorithms for influence maximization in online social networks

Yuqing Zhu (), Weili Wu (), Yuanjun Bi (), Lidong Wu (), Yiwei Jiang () and Wen Xu ()
Additional contact information
Yuqing Zhu: University of Texas at Dallas
Weili Wu: University of Texas at Dallas
Yuanjun Bi: University of Texas at Dallas
Lidong Wu: University of Texas at Dallas
Yiwei Jiang: Zhejiang Sci-Tech University
Wen Xu: University of Texas at Dallas

Journal of Combinatorial Optimization, 2015, vol. 30, issue 1, No 8, 97-108

Abstract: 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$$ 1 − 1 / e , when no size limitation exists on the number of seeds, our algorithm achieves approximation ratio with $$0.857$$ 0.857 , 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$$ 1 − 1 / e 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.

Keywords: Influence maximization; Semidefinite programming; Approximation algorithm (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9635-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:1:d:10.1007_s10878-013-9635-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9635-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().