Time-sensitive influence maximization in social networks

Mohammadi, A, Saraee, MH ORCID: https://orcid.org/0000-0002-3283-1912 and Mirzaei, A 2015, 'Time-sensitive influence maximization in social networks' , Journal of Information Science, 41 (6) , pp. 765-778.

PDF - Accepted Version
Download (881kB) | Preview


One of the fundamental issues in social networks is the influence maximization problem, where the goal is to identify a small subset of individuals such that they can trigger the largest number of members in the network. In real-world social networks, the propagation of information from a node to another may incur a certain amount of time delay; moreover, the value of information may decrease over time. So not only the coverage size, but also the propagation speed matters. In this paper, we propose the Time-Sensitive Influence Maximization (TSIM) problem, which takes into account the time dependence of the information value. Considering the time delay aspect, we develop two diffusion models, namely the Delayed Independent Cascade model and the Delayed Linear Threshold model. We show that the TSIM problem is NP-hard under these models but the spread function is monotone and submodular. Thus, a greedy approximation algorithm can achieve a 1 − 1/e approximation ratio. Moreover, we propose two time-sensitive centrality measures and compare their performance with the greedy algorithm.We evaluate our methods on four real-world datasets. Experimental results show that the proposed algorithms outperform existing methods, which ignore the decay of information value over time.

Item Type: Article
Schools: Schools > School of Computing, Science and Engineering
Journal or Publication Title: Journal of Information Science
Publisher: SAGE
ISSN: 0165-5515
Related URLs:
Funders: Non funded research
Depositing User: Prof. Mo Saraee
Date Deposited: 30 Nov 2015 14:40
Last Modified: 15 Feb 2022 20:01
URI: https://usir.salford.ac.uk/id/eprint/37193

Actions (login required)

Edit record (repository staff only) Edit record (repository staff only)


Downloads per month over past year