Cover Image

Minimum budget for misinformation detection in online social networks with provable guarantees

Q1

Saved in:
Bibliographic Details
Main Author: Canh V. Pham
Other Authors: Dung V. Pham
Format: Article
Language:English
Published: Optimization Letters 2021
Subjects:
Online social network
Misinformation detection
Approximation algorithms
Online Access:https://link.springer.com/article/10.1007/s11590-021-01733-0
https://dlib.phenikaa-uni.edu.vn/handle/PNK/1883
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:localhost:PNK-1883
record_format dspace
spelling oai:localhost:PNK-18832022-08-17T05:54:43Z Minimum budget for misinformation detection in online social networks with provable guarantees Canh V. Pham Dung V. Pham Bao Q. Bui Anh V. Nguyen Online social network Misinformation detection Approximation algorithms Q1 Misinformation detection in Online Social Networks has recently become a critical topic due to its important role in restraining misinformation. Recent studies have showed that machine learning methods can be used to detect misinformation/fake news/rumors by detecting user’s behaviour. However, we can not implement this strategy for all users on a social network due to the limitation of budget. Therefore, it is critical to optimize the monitor/sensor placement to effectively detect misinformation. In this paper, we investigate Minimum Budget for Misinformation Detection problem which aims to find the smallest set of nodes to place monitors in a social network so that detection function is at least a given threshold. Beside showing the inapproximability of the problem under the well-known Independent Cascade diffusion model, we then propose three approximation algorithms including: Greedy, Sampling-based Misinformation Detection and Importance Sampling-based Misinformation Detection. Greedy is a deterministic approximation algorithm which utilizes the properties of monotone and submodular of the detection function. The rest is two randomized algorithms with provable guarantees based on developing two novel techniques (1) estimating detection function by using the concepts of influence sample and importance influence sample with proof of correctness, and (2) an algorithmic framework to select the solution with theoretical analysis. Experiments on real social networks show the effectiveness and scalability of our algorithms. 2021-06-21T02:40:42Z 2021-06-21T02:40:42Z 2021 Article Working Paper https://link.springer.com/article/10.1007/s11590-021-01733-0 https://dlib.phenikaa-uni.edu.vn/handle/PNK/1883 10.1007/s11590-021-01733-0 en Optimization Letters
institution Digital Phenikaa
collection Digital Phenikaa
language English
topic Online social network
Misinformation detection
Approximation algorithms
spellingShingle Online social network
Misinformation detection
Approximation algorithms
Canh V. Pham
Minimum budget for misinformation detection in online social networks with provable guarantees
description Q1
author2 Dung V. Pham
author_facet Dung V. Pham
Canh V. Pham
format Article
author Canh V. Pham
author_sort Canh V. Pham
title Minimum budget for misinformation detection in online social networks with provable guarantees
title_short Minimum budget for misinformation detection in online social networks with provable guarantees
title_full Minimum budget for misinformation detection in online social networks with provable guarantees
title_fullStr Minimum budget for misinformation detection in online social networks with provable guarantees
title_full_unstemmed Minimum budget for misinformation detection in online social networks with provable guarantees
title_sort minimum budget for misinformation detection in online social networks with provable guarantees
publisher Optimization Letters
publishDate 2021
url https://link.springer.com/article/10.1007/s11590-021-01733-0
https://dlib.phenikaa-uni.edu.vn/handle/PNK/1883
_version_ 1751856254922260480
score 8.887836

Similar Items