LCPM-UP: Achieving Scalable Precision Marketing via Limited Diffusion Models

TL;DR

Precision marketing in social networks often fails because it ignores two realities: users have diverse profiles, and information influence "dies out" after too many hops. This paper proposes the LCPM-UP problem and the LD-IC model to address this. To make it practical for millions of users, they introduce TU-LIH, a heuristic that cuts computation time from 10+ hours to 60 minutes with minimal loss in accuracy.

Background & Positioning

In the academic coordinate system, this work sits at the intersection of Influence Maximization (IM) and User Profiling. While traditional SOTA methods focus on Influence Maximization (maximizing reach with fixed seeds), this paper tackles the dual Minimum Seed Set problem: how to reach a specific quota ($J$) of target users with the lowest possible cost.

The Core Problem: Why Traditional Models Fail

Most prior works rely on the standard Independent Cascade (IC) model. The authors point out two fatal flaws for real-world applications:

1. Interest Blindness: They assume all nodes are equally valuable. In reality, a "high-end moisturizer" campaign only cares about "high-income women," not the entire graph.
2. Infinite Propagation Fallacy: IC models theoretically allow information to flow indefinitely. However, physical intuition and data (e.g., Twitter reply trees) show that influence dissipates rapidly as the path length increases.

Methodology: LD-IC and the TU-LIH Heuristic

1. The LD-IC Model (Limited Diffusion)

The authors define a Probability Threshold $heta$. For any propagation path $P$, the probability $Pa(P)$ is the product of edge weights. If $Pa(P)<heta$, the "word-of-mouth" chain breaks. This adds a realistic physical constraint to the simulation.

2. The TU-LIH Algorithm

Since calculating exact influence in this model is NP-hard, the authors use a greedy approach. But since standard greedy (Monte Carlo) is too slow, they propose the Target User Local Influence Heuristic (TU-LIH).

The Intuition: instead of simulating the whole network, we only look at the Maximum Probability Path (MPP). By building a local "influence tree" for each node, we can estimate incremental gain using a linear relationship: $ap(u)=t(u,x)\cdot ap(x)+\beta (x,u)$ This allows the algorithm to update influence scores without re-running thousands of simulations.

Figure 1: In the LD-IC model, Path B-C fails as it drops below the threshold, preventing wasteful seed expenditure on unreachable nodes.

Experiments & Results

The authors tested their approach on four datasets: IMDB, DBLP, Harvard (Facebook), and Patent Information.

Efficiency at Scale

On the Patent Information dataset (100,000 nodes):

• Greedy Algorithm: > 10 hours.
• TU-LIH: ~1 hour.
• Efficiency: TU-LIH achieved a 10x speedup while maintaining a seed set size nearly identical to the Greedy baseline.

Precision vs. Baselines

When the goal was to influence 90% of target users ($J=0.9$), the Highest Degree and Random heuristics required nearly 5 times more seeds than TU-LIH. This proves that "being popular" (high degree) is not the same as "being influential to a specific demographic."

Figure 2: Performance across 4 datasets showing TU-LIH (red) closely tracking the optimal Greedy (black) while far-outperforming baselines.

Critical Insight & Takeaways

The most profound takeaway from this paper is the validation of local influence. By proving the submodularity of the LD-IC model, the authors provide a theoretical safety net for using greedy-based heuristics.

Limitations:

• The model assumes user profiles are static and accurately known, which is rarely the case in dynamic social streams.
• The $O(n_{Ta}\cdot t_v)$ complexity still scales with the number of target users, which might remain high in global-scale applications.

Future Direction: The next frontier is Competitive Precision Marketing—how do you minimize cost when a competitor is simultaneously trying to influence the same target users with a different profile?

Technical Editor's Note: This paper is a must-read for engineers building recommendation engines or automated ad-buying platforms where cost-per-acquisition (CPA) is the primary metric.