Opinion-aware Influence Maximization in Online Social Networks

Influence maximization (IM) is essential for viral marketing in online social networks (OSNs). Given an OSN represented as a graph, IM finds a set of nodes (users) as “seeds” to initiate a promotion campaign so that the spread of information through word-of-mouth propagation among users is maximized. Previous IM approaches mainly focus on maximizing the total influence spread across the OSN. They assume that all users are potential customers and more exposure can lead to higher profits. However, in real-world scenarios, users who dislike an item may express and spread negative opinions about it, thus lowering the benefits of promotion. In this paper, we study an opinion-aware influence maximization (OIM) problem that selects a set of k seed users to maximize the positive opinions about a target item and minimize the negative opinions about it in an OSN. Given that the sets of users with positive, neutral, and negative opinions about the target item are obtained from historical data, we design a novel algorithm for OIM that consists of an opinion-aware influence estimation scheme based on reverse reachable sets and a seed set selection method based on sandwich approximation. Theoretically, although OIM is NP-hard and non-submodular, our algorithm still has a data-dependent approximation factor. Empirically, by performing extensive experiments on several real-world datasets, we show that our algorithm boosts the spread of positive opinions while limiting the spread of negative opinions compared to existing IM algorithms.