Rumor blocking with pertinence set in large graphs

Online social networks facilitate the spread of information, while rumors can also propagate widely and fast, which may mislead some users. Therefore, suppressing the spread of rumors has become a daunting task. One of the widely used approaches is to select users in the social network to spread the truth and compete against the rumor, so that users who receive the truth before receiving rumors will not trust or propagate the rumor. However, the existing works only aim to speed up blocking rumors without considering the pertinency of users. For example, consider a social media platform operator aiming to enhance user online safety. Based on the user’s online behavior, the users who are at high risk should be alerted first. Motivated by this, we formally define the rumor blocking with pertinence set (RBP) problem, which aims to find a truth seed set that maximizes the number of nodes affected by truth and ensures that the number of influenced nodes within the pertinence set reaches at least a given threshold. To solve this problem, we design a hybrid greedy framework (HGF) algorithm with local and global phases. We prove that HGF can provide a (1 - 1 / e- ϵ) -approximate solution with high probability while reducing the cost of the sampling process. Extensive experiments on 8 real social networks demonstrate the efficiency and effectiveness of our proposed algorithms.