Minimum budget for misinformation blocking in online social networks (Q2279752)

This paper presents minimum budget for misinformation blocking in online social networks. Based on a dual problem characterization, it focuses on seeking the smallest set of vertices whose removal from a social network reduces the influence of misinformation spread to at least a threshold \(\gamma\). This problem is referred to as targeted misinformation blocking problem. It is proved that the targeted misinformation blocking problem is \(\#P\)-hard under the linear threshold model and it is \(NP\)-hard when the network is a directed acyclic graph under the independent cascade model. Under the linear threshold model, it is proved that the objective function is monotone and sub-modular function. A nature greedy algorithm is proposed and gives a ratio of \(1+\ln(\gamma/\epsilon)\). Some experiments are built on a variety of real-world social networks.