Interaction-Aware Influence Maximization and Iterated Sandwich Method

摘要

Influence maximization problem has been studied extensively with the development of online social networks. Most of the existing works focus on the maximization of influence spread under the assumption that the number of influenced users determines the success of a product promotion. However, the profit of some products such as online game depends on the interactions among users besides the number of users. In this paper, we take both the number of active users and the user-to-user interactions into account and propose the interaction-aware influence maximization problem. To address this practical issue, we analyze its complexity and modularity, propose the sandwich theory which is based on decomposing the non-submodular objective function into the difference of two submodular functions and design iterated sandwich algorithm which is guaranteed to get data dependent approximation solution.