Effector Detection Problem in Social Networks

摘要

Nowadays, different innovations spread rapidly in online social networks. An activation state can indicate whether each user adopts the target information. The effector detection problem aims to find a way to generate an activation state as close to an observed one as possible. In this article, based on the influence spread, the unconstrained and constrained effector detection problems are proposed. To tackle them, we design two approximation algorithms since the problem is NP-hard, and the objective function is nonsubmodular. For the unconstrained case, our objective function can be best provided with the difference of two submodular functions. Thus, we address this problem through the modular-modular algorithm. For the constrained case, we devise the solutions for the original function, submodular upper bound, and lower bound according to an idea of reverse influence sampling. Then, there is a data-dependent approximate solution using the sandwich approximation algorithm. Finally, we show the correctness and superiority of our methods through massive experiments in three real-world networks.