Beyond Binary Influence: Multi-State Diffusion for Targeted Social Advertising

TL;DR

This research tackles the gap between academic Influence Maximization (IM) and real-world Social Advertising. By introducing an "Assimilative" state—users who are influenced but don't reshare—and a probability model driven by Attention, Intimacy, and Share (AIS) scores, the authors achieve a 61% to 108% improvement in influence spread over traditional SOTA methods like Weighted Cascade and degree-based selection.

Problem & Motivation: The Binary Trap

In the classic IM literature, users are either "Active" (influenced and spreading) or "Inactive" (uninfluenced). However, in social marketing, there is a massive "silent majority": users who see an ad, become interested in the product (assimilated), but simply do not click "share" on their profile.

The authors argue that:

1. Binary states are insufficient: We must distinguish between those who are effectively advertised to (Assimilative) versus those who act as hubs (Active).
2. Probabilities are not random: Most IM papers assign random weights or use $1/in\_degree$. Real influence depends on whether the user likes the product category (Attention), their bond with the source (Intimacy), and their habit of sharing (Share).

Methodology: The AIS Framework

The core of the paper is the Multi-State Diffusion Model. Unlike the Independent Cascade (IC) or Linear Threshold (LT) models, this framework splits the "influenced" population into two distinct categories.

1. The Three States

2. The Probability Triple

The transition probability from user $u$ to $v$ for item $i$ is calculated using:

• Attention Score ($AS$): Uses Word2Vec and a weighted bipartite graph matching to compare the user's historical keywords with the advertisement's keywords.
• Intimacy Score ($IS$): Normalized count of interactions (Likes, Comments) between the user pair.
• Share Score ($SS$): The inherent probability of user $v$ to share any content, based on past behavior.

Figure 1: The diffusion flow. Notice how state $v$ is determined by the intersection of attention, intimacy, and the tendency to share.

3. Optimization

To make this scalable for large networks like Naver Blog (2.3M nodes), the authors employed Path-Based IM (PB-IM) to avoid expensive Monte-Carlo simulations and used the CELF (Cost-Effective Lazy Forward) algorithm to exploit submodularity, reducing redundant calculations by up to 700x.

Experiments & Results

The authors validated their model using a massive dataset from Naver Blog.

SOTA Comparison

In tests involving products like "Strollers" and "Ramen," the proposed approach (PR) vastly outperformed industry-standard heuristics:

• vs. SDD (Single Degree Discount): +61% spread.
• vs. WC (Weighted Cascade): +108% spread.
• vs. FO (Follower-based): +61% spread.

Figure 2: Influence spread comparison across various methods. The proposed method (PR) demonstrates superior scalability and reach as the number of agents increases.

User Study: The Human Touch

Beyond math, 15 human evaluators reviewed the selected agents. The proposed method scored significantly higher across:

• Q1 (Attention): Relevance of the agent to the specific item.
• Q2 (Spread): Perceived capability to influence others.
• Q3 (Overall): Practical marketing value.

Critical Insight & Conclusion

The true value of this work lies in the Assimilative state. In social advertising, the goal isn't just to make content "go viral" (Active); it's to ensure the right people see it (Assimilative). By maximizing the combined set of Active and Assimilative users, the model provides a more accurate metric for Return on Ad Spend (ROAS) than traditional IM models.

Future Outlook: While powerful, the model relies on keyword-based similarity. Integrating deep visual features (analyzing photos of products in posts) could further enhance the Attention Score for modern platforms like Instagram or TikTok.