Influence persistence maximization in temporal social networks

Publication Type

Journal Article

Publication Date

7-2026

Abstract

In this paper, we investigate a novel Influence Persistence Maximization (InfPM) problem in temporal social networks. Given a temporal graph, InfPM aims to identify a fixed seed node set S that maximizes the total duration of persistent influence across consecutive snapshots. After proving that InfPM is NP-hard, monotonic, and non-submodular, we develop two efficient solutions: (1) RevG, a reverse greedy algorithm that iteratively removes low-contribution nodes, and (2) LRep, a replacement-based method that progressively improves the quality of seed node set. To accelerate influence computation in RevG and LRep, we propose a new influence computation method integrating snapshot compression, probability-aware sampling, and a specialized influence estimator offering unbiased estimation. Additionally, we explore a practical variant of InfPM, termed Win-InfPM, which relaxes the requirement of consecutive snapshots by introducing a flexible time window model. Extensive experiments on seven real-world networks demonstrate that (1) RevG and LRep effectively identify high-quality seed nodes, achieving up to 100% improvement in total influence persistence over the baselines; and (2) the proposed influence computation method improves the efficiency of RevG and LRep by up to 400%, while maintaining comparable influence persistence.

Keywords

persistence maximization, temporal social networks, theoretical analysis

Discipline

Artificial Intelligence and Robotics | Databases and Information Systems

Research Areas

Intelligent Systems and Optimization

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

38

Issue

7

First Page

4419

Last Page

4433

ISSN

1041-4347

Identifier

10.1109/TKDE.2026.3690643

Publisher

Institute of Electrical and Electronics Engineers

Additional URL

https://doi.org/10.1109/TKDE.2026.3690643

This document is currently not available here.

Share

COinS