Minimum budget for misinformation blocking in online social networks

Preventing misinformation spreading has recently become a critical topic due to an explosive growth of online social networks. Instead of focusing on blocking misinformation with a given budget as usually studied in the literatures, we aim to find the smallest set of nodes (minimize the budget) whose removal from a social network reduces the influence of misinformation (influence reduction) greater than a given threshold, called the Targeted Misinformation Blocking problem. We show that this problem is #P-hard under Linear Threshold and NP-hard under Independent Cascade diffusion models. We then propose several efficient algorithms, including approximation and heuristic algorithms to solve the problem. Experiments on real-world network topologies show the effectiveness and scalability of our algorithms that outperform other state-of-the-art methods.