Time-aware influence minimization via blocking social networks

Publication Type

Conference Proceeding Article

Publication Date

5-2025

Abstract

In this paper, we investigate the Time-aware Influence Minimization (TIMIN) problem in social networks, focusing on minimizing negative influence concerning a critical deadline by temporarily blocking specific nodes in the given social network. First, we introduce the Temporal Linear Threshold (TLT) model, a novel framework that incorporates time delay in influence propagation, the decay of influence power over time, and the lifecycle of influence. Building on this model, we formally define the Timin problem and prove its NP-hardness, monotonicity, and supermodularity. To tackle the Timin problem, we develop the Timin-Greedy, a greedy algorithm that achieves (1 −1/e) approximation. Since exact computation of negative influence spread for any node set in Timin-Greedy is #P-hard, we propose TESTIM, a scalable implementation that provides (1−1/e−ϵ) approximation. To further enhance the efficiency, we introduce NReplacer, a heuristic algorithm leveraging the insight that potential blocking nodes often cluster near the negative source. Our extensive experimental evaluations demonstrate several key findings: (1) TESTIM is up to 10× faster than the baselines while achieving 30%–50% more reductions in negative influence spread, and (2) NReplacer exhibits a 5× speedup compared to TESTIM, with comparable reductions in negative influence spread.

Discipline

Applied Behavior Analysis | Social Psychology

Publication

Proceeding of the 2025 IEEE 41st International Conference on Data Engineering (ICDE), Hong Kong, May 19-23

First Page

557

Last Page

570

Identifier

10.1109/ICDE65448.2025.00048

Publisher

IEEE Computer Society

City or Country

Washington, DC

Additional URL

https://doi.org/10.1109/ICDE65448.2025.00048

This document is currently not available here.

Share

COinS