Target Influence Maximization Against Overexposure Under Threshold-Dependent Model in Online Social Networks
摘要
Recently, viral marketing campaigns leverage the power of word-of-mouth, a strategy whose efficacy can be negatively affected by overexposure. Existing studies exploited the extended independent cascade (IC) model, while the essence of overexposure highly relies on the cumulative impact from its neighbors, which is a feature of the linear threshold (LT) model. Therefore, this paper proposes a novel threshold-dependent(TD) model that captures overexposure in target influence maximization(TIM) problem, aiming to select at most k nodes as advocates such that the expected positive influence on target users is maximized eventually. In this model, each node randomly generates a threshold window including activation and overexposure threshold. An inactive node is positively activated if the total weight of its active in-neighbors is within its threshold window. Since the resulting influence function in TD model is non-monotone and non-submodular, we analyze the approximation ratio of incremental greedy algorithm with suboptimal performance. Then, we develop a variant of sandwich approximation algorithm with theoretical analysis. This novel sandwich framework exploits an upper bound function, holding the form of the difference of two submodular functions, and a lower submodular bound function.