Who Influences Me? Moving from Global to Personalized Influence Maximization

TL;DR

In social networks, "global influencers" (like celebrities) are often irrelevant to your personal decisions. This paper shifts the paradigm from global influence to Personalized Influence Maximization (PIM), providing a mathematical framework and efficient algorithms to find the $k$ nodes that have the highest probability of activating a specific target user.

The Problem: The "Celebrity" Bias

Most influence research asks: “How can we start a trend that covers the whole city?” But personalized services (ads, recommendations, search) need to ask: “Who are the top-10 people most likely to influence user $W$?”

The authors prove two counter-intuitive points:

1. Neighbors aren't enough: Your direct friends might not be your biggest influences; often, a "second-nearest" node in a specific cluster carries more weight.
2. Global stars are far away: Global top-k nodes often leave large "blanks" in coverage for specific local users.

Methodology: Solving the Local Optima

The PIM problem is NP-hard because calculating the exact influence probability (the probability that target $w$ is activated by seed set $U$) is #P-hard.

1. The Mathematical Intuition: Variance Reduction

Instead of simple Monte-Carlo simulations (which are high-variance and slow), the authors propose an unbiased estimator for influence degree $R_w(U)$: $R_w(U)={\mathbb{E}}^U\left[1-{\prod }_{v\in Y}(1-p_{vw})\right]$ where $Y$ is the set of activated neighbors of target $w$. This formula essentially looks at the "last hop" of influence, providing a smoother, lower-variance gradient for optimization.

2. Algorithms

• LGA / ELGA (Greedy): By proving that the objective function is sub-modular, the authors show that a greedy "hill-climbing" approach can reach at least ~63% of the optimal solution. ELGA speeds this up by inducing smaller sub-graphs from the original network.
• LCA (Local Cascade Algorithm): For massive networks (like Wikipedia with 2.3M nodes), the authors ignore long, weak paths and focus only on the shortest-path community between potential seeds and the target.

Figure 1: Comparison showing why local influencers (node u) outperform global ones (node m) for target w.

Experiments & SOTA Comparison

The authors tested their methods against standard baselines like Global Degree and Local Neighbors.

• Accuracy: The greedy algorithms (LGA/ELGA) consistently beat the competition. On the Weibo dataset, they outperformed global degree methods by over 120% in successfully reaching the target.
• Scalability: While the greedy method is accurate, it is slow ($1,326,346$ms in some tests). The LCA heuristic, however, provided nearly the same accuracy in just 15ms, a massive leap for real-time applications.

Figure 2: Influence degree comparison showing LGA/ELGA/LCA outperforming traditional global heuristics.

Critical Analysis & Conclusion

The value of this work lies in its scalability. By recognizing that social influence is "decaying" over distance, the authors justify ignoring the majority of a graph to focus on a target’s local neighborhood.

Limitations:

• The model assumes the "Independent Cascade" (IC) model, where each "push" is an independent event. In reality, social influence often requires reinforcement (Complex Contagion), which this paper doesn't address.
• The temporal aspect—how influence changes over time—is left as future work.

Takeaway for Practitioners: If you are building a recommendation engine, stop looking for the "Katy Perry" of your graph. Use the LCA approach to map shortest-path communities around your users to find the hidden "micro-influencers" that actually drive their behavior.