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