Maximizing misinformation restriction within time and budget constraints

Online social networks have become popular media worldwide. However, they also allow rapid dissemination of misinformation causing negative impacts to users. With a source of misinformation, the longer the misinformation spreads, the greater the number of affected users will be. Therefore, it is necessary to prevent the spread of misinformation in a specific time period. In this paper, we propose maximizing misinformation restriction ( $$\mathsf {MMR}$$ MMR ) problem with the purpose of finding a set of nodes whose removal from a social network maximizes the influence reduction from the source of misinformation within time and budget constraints. We demonstrate that the $$\mathsf {MMR}$$ MMR problem is NP-hard even in the case where the network is a rooted tree at a single misinformation node and show that the calculating objective function is #P-hard. We also prove that objective function is monotone and submodular. Based on that, we propose an $$1{-}1/\sqrt{e}$$ 1 - 1 / e -approximation algorithm. We further design efficient heuristic algorithms, named $$\mathsf {PR}$$ PR - $$\mathsf {DAG}$$ DAG to show $$\mathsf {MMR}$$ MMR in very large-scale networks.