Minimum budget for misinformation blocking in online social networks
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.
- Maximizing misinformation restriction within time and budget constraints
- Minimum budget for misinformation detection in online social networks with provable guarantees
- Community-based rumor blocking maximization in social networks: algorithms and analysis
- Minimizing the Spread of Rumor Within Budget Constraint in Online Network
- Community-based rumor blocking maximization in social networks
- Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
- Complexity of finding dense subgraphs
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- scientific article; zbMATH DE number 1931795 (Why is no real title available?)
- Maximizing misinformation restriction within time and budget constraints
- The Complexity of Enumeration and Reliability Problems
- Maximizing misinformation restriction within time and budget constraints
- Community-based rumor blocking maximization in social networks
- Minimum budget for misinformation detection in online social networks with provable guarantees
- Community-based rumor blocking maximization in social networks: algorithms and analysis
- Improved x-space algorithm for min-max bilevel problems with an application to misinformation spread in social networks
- Optimal containment of misinformation in social media: a scenario-based approach
- Minimizing the Spread of Rumor Within Budget Constraint in Online Network
- Contrasting the spread of misinformation in online social networks
- Misinformation influence minimization problem based on group disbanded in social networks
- A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities
- Fast approximation algorithm for non-monotone DR-submodular maximization under size constraint
- Efficient parallel algorithm for minimum cost submodular cover problem with lower adaptive complexity
- Practical algorithm for minimum cost submodular cover problem with performance guarantees
This page was built for publication: Minimum budget for misinformation blocking in online social networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279752)
