Targeted Influence Maximization in Social Networks

Influence maximization (IM) problem asks for a set of k nodes in a given graph G, such that it can reach the largest expected number of remaining nodes in G. Existing methods have either considered that the influence be targeted to meet certain deadline constraint, or be restricted to specific geographical region. However, if an event organizer wants to disseminate some event information on a social platform, s/he would want to select a set of users who can influence the most number of people within the neighborhood of the event location, and this influence should occur before the event takes place. Considering the location and deadline independently may lead to a less than optimal set of users. In this paper, we formalize the problem targeted influence maximization in social networks. We adopt a login model where each user is associated with a login probability and he can be influenced by his neighbors only when he is online. We develop a sampling based algorithm that returns a (1-1/e-ε)-approximate solution, as well as an efficient heuristic algorithm that focuses on nodes close to the target location. Experiments on real-world social network datasets demonstrate the effectiveness and efficiency of our proposed method.