ALDAG: Rethinking Influence Maximization with "Passive Acceptance" in Social Networks

TL;DR

Most Influence Maximization (IM) models assume that if you influence a friend, they will definitely tell their friends. This paper argues that’s wrong. By distinguishing between Active users (who retweet) and Accepted users (who just "like"), the authors propose the ALT Model and the ALDAG algorithm, boosting influence prediction accuracy by up to 174% on large-scale networks.

Context: The "Like" vs. "Retweet" Dilemma

In the classical IM framework, influence is binary: a node is either activated or not. However, social media reality is more nuanced. Think of Twitter: many people "Like" a post (they are influenced by it) but do not "Retweet" it (they don't propagate it).

The authors identify a critical gap: Trust levels are diverse. If we ignore the "Accepted" group—those who reached the threshold to believe the info but lacked the motivation to share it—we are essentially flying blind in viral marketing.

Methodology: The Accepted Linear Threshold (ALT) Model

The authors extend the classic Linear Threshold (LT) model into the ALT model. Each edge $(u,v)$ now has two weights:

• $b_{uv}^{act}$: The weight for activation (propels further sharing).
• $b_{uv}^{acc}$: The weight for acceptation (internalizes the message).

A node $v$ transitions through states: Inactive $\to$ Accepted $\to$ Active. Crucially, only Active nodes contribute to the cumulative weight needed to move their neighbors.

The ALDAG Algorithm

To handle massive graphs where Monte-Carlo simulations fail, the authors propose ALDAG. It builds on the idea of Local Directed Acyclic Graphs (LDAG).

1. Local Scoping: For each node, it constructs a local neighborhood of influence (LDAG) where the probability of influence remains above a certain threshold.
2. Edge Coloring Intuition: The authors use a clever "Edge Coloring" proof to show that influence spread is still submodular under ALT, justifying a greedy approach.
3. Recursive Update: As shown in the following logic, the algorithm calculates the incremental influence spread by accounting for both activation and acceptance probabilities across the valid paths.

Experiments: Superior Spread and Scalability

The authors tested ALDAG against heavyweights like IMM, OPIM, and SIMPATH.

1. Influence Spread (Effectiveness)

In every dataset, from small citation networks (NetHEPT) to massive social graphs (LiveJournal), ALDAG found seed sets that generated significantly more total influence. The "Relevant Improvement" was most pronounced when the gap between activation and acceptation was large.

2. Efficiency

While ALDAG is more complex than basic LT-based heuristics, it maintains near-linear scalability. On the Patent dataset (~3.8M nodes), it remains competitive with SOTA algorithms while providing a much "richer" influence result.

Critical Insight & Conclusion

The fundamental contribution here isn't just a faster algorithm; it's a more realistic model of human psychology in social networks. By proving that the AIM problem remains NP-hard yet submodular, the authors provide a rigorous mathematical floor for this more complex reality.

Takeaway: If you are designing a viral marketing campaign, stop optimizing for "Shares" alone. Understanding who "Accepts" the message without sharing it provides a more accurate map of your true brand reach.

Limitations: The model assumes activation and acceptation are independent behaviors, which may not hold true in highly polarized environments. Future work should look at how these behaviors correlate over time.