Efficient and cost-effective influence and blocker minimization

Abstract

Online social networks have emerged as prominent platforms for individuals to rapidly share ideas and perspectives. However, their swift dissemination capabilities also make them powerful channels for the spread of misinformation. Such dissemination results in substantial economic and societal harm, highlighting the need for effective suppression. To support this practical demand, this paper investigates the influence minimization (IMIN) and blocker minimization (BM) problems. The IMIN problem aims to find a node set of size k (the given budget) to block, such that the reduction in influence spread of a given seed set S is maximized. The BM problem is the dual of IMIN, aiming to find a node set of minimum cardinality to block, such that the threshold condition is satisfied, i.e., the reduction in influence spread of S is not less than the given threshold η\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\eta $$\end{document}. Both problems are NP-hard and involve a non-submodular objective function. Existing IMIN solutions incur high computational costs and offer no approximation guarantees on influence spread reduction. To fill the gap, we build upon the sandwich strategy to develop the first efficient algorithm with data-dependent approximation guarantees for IMIN. In particular, we design non-trivial (1-1/e-ϵ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1-1/e-\epsilon )$$\end{document}-approximation algorithms to optimize the proposed submodular bounding functions. For the BM problem, the existing solution is of limited effectiveness and lacks theoretical guarantees for both node set cardinality and threshold condition satisfaction. In this paper, we design a heuristic and two bicriteria approximation algorithms to address the BM problem. The heuristic is efficient and satisfies the threshold condition, but fails to ensure near-optimal cardinality. The two approximation algorithms both provide guarantees on cardinality: the first attains a tighter approximation ratio at the expense of efficiency, while the second yields a slightly weaker ratio with improved efficiency. Finally, comprehensive experiments on 9 real-world datasets are conducted to validate the efficiency and effectiveness of the proposed techniques.