Minimum budget for misinformation detection in online social networks with provable guarantees
Q1
Lưu vào:
| Tác giả chính: | |
|---|---|
| Đồng tác giả: | |
| Định dạng: | Bài Báo |
| Ngôn ngữ: | English |
| Nhà xuất bản: |
Optimization Letters
2021
|
| Chủ đề: | |
| Truy cập trực tuyến: | https://link.springer.com/article/10.1007/s11590-021-01733-0 https://dlib.phenikaa-uni.edu.vn/handle/PNK/1883 |
| Từ khóa: |
Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
|
| 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 |