Skip to the content

Time-sensitive influence maximization in social networks

Mohammadi, A, Saraee, MH and Mirzaei, A 2015, 'Time-sensitive influence maximization in social networks' , Journal of Information Science, 41 (6) , pp. 765-778.

[img]
Preview
PDF - Accepted Version
Download (881kB) | Preview

Abstract

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: Dr Mo Saraee
Date Deposited: 30 Nov 2015 14:40
Last Modified: 21 Dec 2015 09:03
URI: http://usir.salford.ac.uk/id/eprint/37193

Actions (login required)

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

Downloads

Downloads per month over past year