Thời gian: từ 9h00 đến 10h00 sáng thứ 4 ngày 30/03/2022 theo hình thức trực tuyến.

Link seminar: meet.google.com/gaq-qqdn-wzh

Tóm tắt: Misinformation detection in Online Social Networks has recently become a critical topic due to its important role in restraining misinformation. Recent studies have shown that machine learning methods can be used to detect misinformation/fake news/rumors by detecting users’ behaviour. However, we cannot 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 talk, 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.