Time-sensitive influence maximization in social networks

Mohammadi, A; Saraee, MH; Mirzaei, A

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.

Citation

Mohammadi, A., Saraee, M., & Mirzaei, A. (2015). Time-sensitive influence maximization in social networks. Journal of Information Science, 41(6), 765-778. https://doi.org/10.1177/0165551515602808

• Journal Article Type: Article
• Online Publication Date: Nov 20, 2015
• Publication Date: Dec 1, 2015
• Deposit Date: Nov 30, 2015
• Publicly Available Date: Apr 5, 2016
• Journal: Journal of Information Science
• Print ISSN: 0165-5515
• Electronic ISSN: 1741-6485
• Publisher: SAGE Publications
• Volume: 41
• Issue: 6
• Pages: 765-778
• DOI: https://doi.org/10.1177/0165551515602808
• Publisher URL: http://dx.doi.org/10.1177/0165551515602808
• Related Public URLs: https://uk.sagepub.com/en-gb/eur/journal-of-information-science/journal201676