Influence Spreading Path and Its Application to the Time Constrained Social Influence Maximization Problem and Beyond

Bo Liu, Gao Cong, Yifeng Zeng, Dong Xu, Yeow Meng Chee

Research output: Contribution to journalArticlepeer-review

63 Citations (Scopus)
2 Downloads (Pure)

Abstract

Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, is to get a small number of users to adopt a product, which subsequently triggers a large cascade of further adoptions by utilizing “Word-of-Mouth” effect in social networks. Time plays an important role in the influence spread from one user to another and the time needed for a user to influence another varies. In this paper, we propose the time constrained influence maximization problem. We show that the problem is NP-hard, and prove the monotonicity and submodularity of the time constrained influence spread function. Based on this, we develop a greedy algorithm. To improve the algorithm scalability, we propose the concept of Influence Spreading Path in social networks and develop a set of new algorithms for the time constrained influence maximization problem. We further parallelize the algorithms for achieving more time savings. Additionally, we generalize the proposed algorithms for the conventional influence maximization problem without time constraints. All of the algorithms are evaluated over four public available datasets. The experimental results demonstrate the efficiency and effectiveness of the algorithms for both conventional influence maximization problem and its time constrained version.
Original languageEnglish
Pages (from-to)1904-1917
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume26
Issue number8
Early online date24 Jun 2013
DOIs
Publication statusPublished - Aug 2014
Externally publishedYes

Fingerprint Dive into the research topics of 'Influence Spreading Path and Its Application to the Time Constrained Social Influence Maximization Problem and Beyond'. Together they form a unique fingerprint.

Cite this