Reachability-Driven Influence Maximization in Time-dependent Road-social Networks

The influence maximization in a social network has been extensively studied, however, existing works have neglected the fact that time-dependent reachable information plays an important role in this query processing. Many real-world applications, such as location-based recommendations, location-based advertisements, and location-based emergency message distribution, require such a query. In this paper, we formally define reachability-driven influence maximization (RDIM) in time-dependent road-social networks, to find a seed set that maximizes the expected influence over potential users, i.e., target users, who are likely to reach a given location within a deadline. To efficiently compute the influence diffusion, we define a versatile influence (VI) diffusion model based on user relationships and time-dependent location information. The RDIM has two critical challenges: identifying the target users and finding the seed nodes. We propose a TS-index with temporal and regional dimensions for identifying the target users by employing a reachable region. To find seed nodes, we construct a CTS-index by extending a community dimension into the TS-index to enhance the calculation of social influence by using the relationship between communities and the reachable region. Finally, we use the real road and social network data to empirically verify the efficiency and effectiveness of our solutions.