Time-sensitive influence maximization in social networks

A lot of people have been concerned about the problem of maximizing influence in social networks, which is aimed to find a set of nodes to get the influence spread maximized. However, the existing reasearches mainly focus on that a node influences its neighbors once without considering time and cost constraints. But in real world, people often try to influence their friends repeatedly during a time interval. Sometimes, the spread of information will cost a certain price as well. In this paper, we study the Time-sensitive Influence Maximization Problem and propose a Time and Cost constrainted Influence model with users' Online patterns (TCIO model). In TCIO model, the selection of seed nodes is limited to the budget and each node can influence its neighbors repeatedly according to their online patterns with different probability until a given message expire time is reached. We then show that the problem is NP-hard and our model satisfies monotonicity and submodularity for influence spread. Based on this, we develop a greedy algorthm to solve the problem. To reduce the computation complexity and optimize seed node selection with cost, we propose an efficient method GMAI for approximately calculating added influence using influence weight. Our experiments show that our model is effective and practical since it takes into account time factors, and GMAI faster and more effecient than other evaluated algorithms.