IM-Bandit: Conquering the Dynamic Nature of Social Influence

TL;DR

Social networks are not static artifacts; they are living, breathing entities. This paper addresses the Evolving Influence Maximization (IM) problem, where both the network topology and the influence probabilities are unknown and changing. By framing the problem as a Multi-Armed Bandit (MAB) and utilizing a UCB-based learning approach, the authors propose a solution that adaptively selects seeds in rounds, outperforming traditional static algorithms on real-world evolving datasets.

Problem & Motivation: The "Static" Fallacy

Most Influence Maximization (IM) algorithms since Kempe et al. (2003) operate under a "frozen" world assumption: the graph today is the graph tomorrow. However, modern platforms like WeChat or Twitter grow by millions of users monthly.

This evolution introduces two fatal flaws in static IM:

1. Topology Drift: Seeds chosen on Day 1 are disconnected from users who join on Day 10.
2. Probability Blindness: We cannot know the "word-of-mouth" strength (influence probability) of a newly created social link without observing interactions.

Methodology: The Bandit Bridge

The authors bridge this gap by mapping IM into the Bandit domain. Each user is treated as a "base-arm" with an unknown reward distribution (their influence probability).

1. UCB-based Learning

Instead of guessing probabilities, the algorithm tracks every successful and failed influence attempt across links. Using Hoeffding’s Inequality, it calculates an Upper Confidence Bound (UCB) for each user's influence: ${\overline{p}}_u^t=(1-\gamma )\cdot ({\overline{X}}_u^t+{\xi }_u^t)+\gamma \cdot P$ This formula balances Exploitation (using known influential nodes) and Exploration (testing new or uncertain nodes).

2. Multi-Round Seed Selection

Rather than picking all seeds at $T=0$, the framework picks $K$ seeds in each round $t$. It uses the Reverse Reachable (RR) Sets framework, which is currently the gold standard for IM efficiency, to select seeds that cover the most "Reverse Reachable" nodes in the current graph snapshot.

Experiments & Results

The authors tested their method on citation networks from Data Mining (DM) and Artificial Intelligence (AI) fields—natural evolving networks where nodes (papers) and edges (citations) appear over decades.

Key Findings:

• Convergence: The "Regret" (the gap between the algorithm and the theoretical optimum) is sub-linear, meaning the more rounds the algorithm runs, the closer it gets to the ground-truth optimal performance.
• Superiority: In the AI dataset, our solution (IM-Bandit) significantly outperformed IMM and SKIM as years progressed, because it successfully "learned" the value of new emerging papers that static algorithms ignored.

Figure: Influence diffusion size over years under different seed budgets. Note how the performance gap widens as the network grows.

Critical Analysis & Conclusion

Takeaway

The core contribution is the realization that Influence is an online learning problem, not just a combinatorial optimization problem. By adaptively updating beliefs about user influence, marketers can capture the "new waves" of users in a growing network.

Limitations

• Node Vitality: The paper assumes nodes join and stay. In real social networks, nodes also "churn" (leave), which isn't explicitly modeled here.
• Feedback Latency: The model assumes feedback is available at the end of each round. In reality, influence cascades can take a long time to complete, potentially overlapping with the next round.

Future Outlook

Future research could integrate Contextual Bandits, where user features (e.g., bio, interests) help predict the influence probability of a new user even before they interact with their neighbors.