GIM: Why Targeting Individuals is No Longer Enough for Viral Marketing

TL;DR

In modern social networks, decisions are rarely solo acts; they are group consensus. This paper introduces the Group Influence Maximization (GIM) problem, which focuses on activating entire communities rather than isolated nodes. Because this problem breaks the "submodularity" (law of diminishing returns) that most AI algorithms rely on, the authors develop a Sandwich Framework to trap the complex reality between two manageable mathematical bounds, delivering a robust SOTA solution for group-level influence.

The "Group Reality" Motivation

Most marketing algorithms assume every person you influence is an independent win. But consider a group purchase scenario: a deal only triggers if 50% ($\beta =0.5$) of a local community signs up. If you influence 40%, you get zero groups. If you hit 50%, you win the whole group.

This "all-or-something" threshold creates a massive headache for researchers because the objective function becomes non-submodular. In simple terms: adding a seed might be useless now, but incredibly valuable later once a threshold is reached—violating the standard greedy logic.

Methodology: The Sandwich Strategy

To tackle the non-submodularity, the authors don't look at the problem head-on. Instead, they "sandwich" the true objective $\rho (S)$ between two submodular functions:

1. Upper Bound ($\overline{\rho }$): A relaxed version where a group is "activated" if even one member is influenced.
2. Lower Bound ($\underline{\rho }$): A strict version where we only count groups that are highly likely to be activated based on specific node connections.

By solving these two submodular problems using an Extended D-SSA algorithm (incorporating Reverse Influence Sampling), they can estimate the optimal seed set $S$ with theoretical guarantees.

Figure 1: Comparison of seed selection. While $v_1$ activates more total nodes, $v_6$ is a better "Group Influence" seed because it hits the $\beta$ threshold for multiple groups.

Experiments: Breaking Down the Results

The authors tested their framework on datasets like the Facebook-like Forum and Youtube.

• The Beta Effect: As the activation threshold ($\beta$) increases (meaning groups are harder to "flip"), the total number of activated groups drops sharply.
• Greedy vs. Heuristics: The "Max Outdegree" heuristic—a favorite in industry—performed poorly. It turns out "famous" people with many followers often don't have the specific group density required to reach $\beta$ thresholds.

Figure 2: Performance on Scientific Collaboration networks. The Greedy and Sandwich-based approaches show a clear lead over simple coverage or degree heuristics as seed size increases.

Critical Insight: The "Tipping Point" Logic

The core takeaway for AI and social science is that influence is non-linear. A node that seems "uninfluential" in a global sense might be a "linchpin" for a specific community. The GIM framework proves that if we want to change behavior in a society of groups, we must identify nodes that help communities cross their internal threshold, not just nodes that broadcast to the void.

Conclusion & Future Work

The GIM problem marks a shift toward more realistic social modeling. While the Sandwich Framework provides a strong theoretical anchor, the next frontier will be Dynamic GIM—how do we find these seeds when group memberships and thresholds change in real-time? For now, this work provides the most solid algorithmic foundation for group-targeted viral marketing.

Limitations: The model assumes we know the group structures ($U$) perfectly, which in many stealthy social networks (like encrypted messaging groups), remains a major data hurdle.