Misinformation influence minimization problem based on group disbanded in social networks

Abstract The booming development of online social media has changed the way people post and access information. The authenticity of content is weakened, and all kinds of misinformation on social media spread rapidly. In Online Social Networks (OSN), users arbitrarily form private groups/communities, which greatly increase the exposure rate of misinformation. Considering that echo chamber effect of groups wildly exists, this paper studies the disbanding strategy of private groups in OSNs to Minimize the Spread of Misinformation under the effect of Echo chamber effect (MSME). Given a directed acyclic OSN G ( V , E , C ) , C denotes a set of private groups, the problem of MSME is to select K groups from C , such that the spread of misinformation will be minimized by disbanding these groups. We prove the problem of MSME is NP-hard, then prove that the objective function computation of the problem of MSME is #P-hard. It is proved that the objective function of the problem of MSME is neither a submodular nor a supermodular. A greedy algorithm is constructed and several heuristic algorithms are proposed to solve the objective function which is non-submodular and non-supermodular. Our experimental simulation on four real world datasets verifies the effectiveness of our constructed algorithm.