Location-Aware Influence Blocking Maximization in Social Networks

Abstract

In real social networks, it is often the case that opposite opinions, ideas, products, or innovations are propagating simultaneously. Although the competitive influence problem has been extensively studied, existing works neglect the fact that the location information can play an important role in influence propagation. In this paper, we study the location-aware influence blocking maximization (LIBM) problem, which aims to find a positive seed set to maximize the blocked negative influence for a given query region. In order to overcome low efficiency of the greedy algorithm, we propose two heuristic algorithms LIBM-H and LIBM-C based on the quadtree index and the maximum influence arborescence structure. Experimental results on real-world datasets show that both LIBM-H and LIBM-C are able to achieve a matching blocking effect to the greedy algorithm and often better than other heuristic algorithms, whereas they are several orders of magnitude faster than the greedy algorithm.