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

Liu, Bo, Cong, Gao, Zeng, Yifeng, Xu, Dong and Chee, Yeow Meng (2014) Influence Spreading Path and Its Application to the Time Constrained Social Influence Maximization Problem and Beyond. IEEE Transactions on Knowledge and Data Engineering, 26 (8). pp. 1904-1917. ISSN 1041-4347

[img]
Preview
Text
NRL_44743.pdf - Accepted Version

Download (661kB) | Preview
Official URL: https://doi.org/10.1109/TKDE.2013.106

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.

Item Type: Article
Uncontrolled Keywords: Influence spreading path, influence maximization, social network, large scale, time constrained
Subjects: G400 Computer Science
G500 Information Systems
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: Elena Carlaw
Date Deposited: 12 Nov 2020 12:41
Last Modified: 12 Nov 2020 12:45
URI: http://nrl.northumbria.ac.uk/id/eprint/44743

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics