Premium
Location‐aware targeted influence maximization in social networks
Author(s) -
Su Sen,
Li Xiao,
Cheng Xiang,
Sun Chenna
Publication year - 2018
Publication title -
journal of the association for information science and technology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.903
H-Index - 145
eISSN - 2330-1643
pISSN - 2330-1635
DOI - 10.1002/asi.23931
Subject(s) - computer science , maximization , heuristic , tree (set theory) , set (abstract data type) , traverse , approximation algorithm , node (physics) , social network (sociolinguistics) , steiner tree problem , mathematical optimization , social media , algorithm , world wide web , artificial intelligence , mathematics , mathematical analysis , geodesy , structural engineering , engineering , programming language , geography
In this paper, we study the location‐aware targeted influence maximization problem in social networks, which finds a seed set to maximize the influence spread over the targeted users. In particular, we consider those users who have both topic and geographical preferences on promotion products as targeted users. To efficiently solve this problem, one challenge is how to find the targeted users and compute their preferences efficiently for given requests. To address this challenge, we devise a TR‐tree index structure, where each tree node stores users' topic and geographical preferences. By traversing the TR‐tree in depth‐first order, we can efficiently find the targeted users. Another challenge of the problem is to devise algorithms for efficient seeds selection. We solve this challenge from two complementary directions. In one direction, we adopt the maximum influence arborescence (MIA) model to approximate the influence spread, and propose two efficient approximation algorithms with 1 − 1 / e approximation ratio, which prune some candidate seeds with small influences by precomputing users' initial influences offline and estimating the upper bound of their marginal influences online. In the other direction, we propose a fast heuristic algorithm to improve efficiency. Experiments conducted on real‐world data sets demonstrate the effectiveness and efficiency of our proposed algorithms.