Influence Maximization under The Non-progressive Linear Threshold Model

T.-h. Hubert Chan, Li NingFAW 2015 · OpenReview

TL;DR

This paper introduces a more realistic "non-progressive" version of the Linear Threshold (LT) model for influence maximization in social networks, where users can become inactive again. They prove that this new model is generally not submodular, breaking standard greedy algorithms, but crucially, it is submodular for acyclic networks, enabling efficient approximation algorithms.

What Problem Does This Paper Address?

Influence maximization is a key problem in viral marketing and understanding information spread. The goal is to select a small set of initial "seed" users to activate, such that the total number of eventually activated users is maximized, given a budget. The standard Linear Threshold (LT) model, a popular framework for this, assumes that once a user becomes active, they stay active forever (progressive). However, this doesn't reflect real-world scenarios where user engagement can fluctuate. For example, a user might try a product, find it unappealing, and stop using it. This paper addresses this limitation by introducing a non-progressive LT model where users can revert to an inactive state. This makes the model more realistic but also introduces significant theoretical challenges, as the standard submodularity property, which guarantees the effectiveness of greedy algorithms, might no longer hold.

Methods

The authors extend the classic LT model to a non-progressive version. They define influence as the average number of active nodes over a time period, rather than the final count, to account for the dynamic nature of user states.

Their core contributions lie in analyzing the submodularity of the objective function under this new model:

  • Negative Result: They demonstrate that for general networks with cycles, the influence function is not submodular. This is a critical finding because it invalidates the direct application of widely-used greedy algorithms (like hill-climbing) that rely on submodularity for guaranteed performance.
  • Positive Result (Acyclic Networks): The paper's main contribution is proving that for directed acyclic graphs (DAGs), the influence function is submodular and monotone. This is achieved through a clever connection to random walks and a novel "Path Effect Process" that helps manage the complex dependencies introduced by the non-progressive nature.
  • Algorithmic Implications: Because submodularity is established for DAGs, they can leverage existing theoretical results. They show that a deterministic greedy algorithm can achieve a 1/2-approximation, and a randomized algorithm can achieve a (1 - 1/e)-approximation for influence maximization in acyclic networks under their model.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic network structures (directed acyclic graphs, graphs with cycles, graphs with self-loops) to prove its theorems.

Key Insights and Ideas

  • Realism vs. Tractability: The paper highlights a common tension in modeling: increasing realism (non-progressive behavior) often sacrifices theoretical tractability (submodularity).
  • The Importance of Acyclicity: The distinction between cyclic and acyclic networks is crucial. While submodularity is lost in general graphs, it is preserved in DAGs, suggesting that network structure plays a vital role in the effectiveness of influence maximization algorithms.
  • Random Walks as a Tool: The paper ingeniously connects the non-progressive LT model to random walks. This connection, mediated by the "Path Effect Process," is key to proving submodularity in the acyclic case. It shows how seemingly different probabilistic models can be linked to solve complex problems.
  • Breaking Standard Algorithms: The negative result is significant. It forces researchers to reconsider existing influence maximization strategies and develop new approaches for networks with cycles, or to focus on specific network structures where submodularity holds.

Key Results

  • Influence maximization under the non-progressive LT model is NP-hard, even for acyclic networks.
  • The objective function is not submodular in general networks (with cycles).
  • The objective function is submodular and monotone for directed acyclic graphs (DAGs).
  • For DAGs, a deterministic greedy algorithm achieves a 1/2-approximation, and a randomized algorithm achieves a (1 - 1/e)-approximation for influence maximization.

Limitations and Future Work

  • General Networks: The paper's main positive results are for acyclic networks. The challenge of achieving good approximations for networks with cycles remains an open problem. The authors suggest that the non-submodularity in cyclic graphs might require entirely new algorithmic paradigms.
  • Computational Cost: While the paper proves theoretical guarantees for acyclic networks, the practical implementation of these algorithms, especially calculating influence values, can still be computationally expensive. The paper briefly mentions techniques like sampling or lazy evaluation from prior work, hinting at avenues for practical optimization.
  • Model Variations: The paper focuses on uniform costs for transient and permanent nodes. Future work could explore scenarios with varying costs or more complex node behaviors.

Summary updated

Abstract

In the problem of influence maximization in information networks, the objective is to choose a set of initially active nodes subject to some budget constraints such that the expected number of active nodes over time is maximized. The linear threshold model has been introduced to study the opinion cascading behavior, for instance, the spread of products and innovations. In this paper, we we extends the classic linear threshold model [18] to capture the non-progressive be- havior. The information maximization problem under our model is proved to be NP-Hard, even for the case when the underlying network has no directed cycles. The first result of this paper is negative. In general, the objective function of the extended linear threshold model is no longer submodular, and hence the hill climbing approach that is commonly used in the existing studies is not applicable. Next, as the main result of this paper, we prove that if the underlying information network is directed acyclic, the objective function is submodular (and monotone). Therefore, in directed acyclic networks with a specified budget we can achieve 1/2 -approximation on maximizing the number of active nodes over a certain period of time by a deterministic algorithm, and achieve the (1 - 1/e )-approximation by a randomized algorithm.
BibTeX
@inproceedings{chan2015influence,
  author = {T.-H. Hubert Chan and Li Ning},
  title = {{Influence Maximization under The Non-progressive Linear Threshold Model}},
  booktitle = {FAW},
  year = {2015},
  url = {https://openreview.net/forum?id=RvTd7Nxsl3},
}
Figure