Time Constrained Influence Maximization in Social Networks

Bo Liu, Gao Cong, Dong Xu, Yifeng Zeng

2012 · 166 citations · 18 references

Concepts

TL;DR

Influence maximization, a key problem in social networks, has been widely studied for applications such as viral marketing, yet prior work has not addressed time constraints. This study introduces a time‑constrained influence maximization problem and proposes two scalable Influence Spreading Path methods to address it. We formulate the problem, design a greedy algorithm with theoretical guarantees, and introduce two Influence Spreading Path techniques to enhance scalability. The problem is NP‑hard, with a monotone submodular spread function, and experiments on four datasets confirm that the proposed path‑based methods are efficient and effective.

Abstract

Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, is to get a small number of users to adopt a product, which subsequently triggers a large cascade of further adoptions by utilizing "Word-of-Mouth" effect in social networks. Influence maximization problem has been extensively studied recently. However, none of the previous work considers the time constraint in the influence maximization problem. In this paper, we propose the time constrained influence maximization problem. We show that the problem is NP-hard, and prove the monotonicity and submodularity of the time constrained influence spread function. Based on this, we develop a greedy algorithm with performance guarantees. To improve the algorithm scalability, we propose two Influence Spreading Path based methods. Extensive experiments conducted over four public available datasets demonstrate the efficiency and effectiveness of the Influence Spreading Path based methods.

References

18