One of the most significant problems in social networks analysis is influence maximization problem, which aims to find a set of influential nodes. In the real-world social networks, propagation of information from a node to another may incur a certain amount of time delay. In addition, the value of propagated items might reduce in time. Therefore, in this thesis, we propose the Time-Sensitive Influence Maximization (TSIM) problem, which takes into account the time dependence of the information value. We develop two diffusion models, Delayed Independent Cascade (DIC) and Delayed Linear Threshold (DLT) model and prove that the TSIM problem is NP-hard under these models. For solving the TSIM problem, we propose three time-sensitive heuristic methods namely TSDEG, TSPDEG and TSBET as well as two approximation algorithms with approximation ratio, namely GTSIM and RTSIM. We evaluate our methods on five real datasets. The experimental results show that our proposed algorithms outperform conventional influence maximization methods. In addition, comparison of the suggested algorithms shows superiority of RTSIM methods to other algorithms. Specifically, it outperforms other algorithms in terms of propagation value and at the same time it substantially improves upon the second best algorithm, i.e. GTSIM method, in terms of execution time. Key Words Approximation analysis, Influence maximization, Information diffusion, Social networks, Time-Sensitive diffusion
