Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process

By Wei Lu, Ning Zhang. AAAI Conference on Artificial Intelligence, 2012

298 citations recorded by the source corpus.

Influence maximization is a problem of finding a small set of highly influential users in a social network such that the spread of influence under certain propagation models is maximized. In this paper, we consider time-critical influence maximization, in which one wants to maximize influence spread within a given deadline. Since timing is considered in the optimization, we also extend the Independent Cascade (IC) model to incorporate the time delay aspect of influence diffusion in social networks. We show that time-critical influence maximization under the time-delayed IC model maintains desired properties such as submodularity, which allows a greedy algorithm to achieve an approximation ratio of 1-1/e, to circumvent the NP-hardness of the problem. To overcome the inefficiency of the approximation algorithm, we design two heuristic algorithms: the first one is based on a dynamic programming procedure that computes exact influence in tree structures, while the second one converts the problem to one in the original IC model and then applies existing fast heuristics to it. Our simulation results demonstrate that our heuristics achieve the same level of influence spread as the greedy algorithm while running a few orders of magnitude faster, and they also outperform existing algorithms that disregard the deadline constraint and delays in diffusion.

View Paper: https://www.semanticscholar.org/paper/90b7810b1b3693f7d1382f429a69812cbc5e8bde

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Yuchen Li
2. Hung T. Nguyen
3. Ju Fan
4. My T. Thai
5. Yanhao Wang
6. Thang N. Dinh
7. Kian-Lee Tan
8. Youze Tang

Citations in the corpus

• Influence Maximization on Social Graphs: A Survey (2018, methodology): “The discrete-time models [9], [33], [34] extend IC by modeling the diffusion process from one node to another as a discrete random variable over different time steps.”
• Influence Maximization in Near-Linear Time: A Martingale Approach (2015, methodology): “2 Application to Continuous-Time Models The continuous-time independent cascade (CTIC) model [6, 16, 30] assumes that each directed edge e in the social network G is associated with a length distribution L(e).”
• Influence maximization: near-optimal time complexity meets practical efficiency (2014, background): “For simplicity, assume that (i) g2, g3, andg4 are identical tog1, and (ii) the node that RIS samples fromgi (i ∈ [2, 4]) is vi.”
• Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks (2016, background): “Each edge (u, v) ∈ E is associated with a weight w(u, v) ∈ [0, 1] which indicates the probability that u influences v.”