Beyond Individuals: Strategic Group Influence Maximization in Social Networks

TL;DR

In modern social networks, decisions are rarely individual; they are collective. This paper tackles the Group Influence Maximization (GIM) problem—selecting $k$ seeds to activate the maximum number of groups (where a group is "active" only if $\beta \%$ of its members are). The authors propose CMC (a heuristic focusing on group contribution) and IRIS (a group-aware sampling method), significantly outperforming standard out-degree and coverage benchmarks.

Problem & Motivation: Why Groups Matter

Most Influence Maximization (IM) research focuses on the "viral" spread to as many individuals as possible. However, the authors argue that in contexts like presidential elections or corporate procurement, the "Group" is the unit of success.

The challenge lies in the Threshold Effect: A group of 10 people with a 50% threshold requires 5 active members. Influencing 4 members results in zero group activation. This makes GIM a harder, non-linear problem where traditional metrics like "Out-degree" (how many followers you have) lose their predictive power.

Methodology: The Core Algorithms

1. Complementary Maximum Coverage (CMC)

The CMC algorithm is built on a specialized scoring function $f_c(v_i)$. Instead of looking at global reach, it looks at "marginal utility" within a group.

The influence $f_c(v_i)$ is defined as: $f_c(v_i)={\sum }_j\frac{a_{v_i}}{|u_j|-H_{u_j}+1}$

• $a_{v_i}$: How many members in group $j$ can be reached by node $i$.
• $|u_j|-H_{u_j}$: The "slack" or difficulty of the group.

Intuition: CMC favors nodes that can push a group toward its specific tipping point rather than nodes that widely influence individuals across many groups without hitting the activation threshold in any of them.

2. Improved Reverse Influence Sampling (IRIS)

IRIS evolves the classic RIS framework. While standard RIS builds Reverse Reachable (RR) sets to see which nodes are most likely to influence other nodes, IRIS modifies the selection phase.

Above: The logic of generating RR sets. IRIS uses this to select seeds that maximize group-level coverage within these sets.

Experiments & Results

The authors tested their methods on two real-world datasets: LastFM (Dataset1) and Gnutella (Dataset2).

Key Findings:

• CMC Dominance: In almost all undirected graph tests, CMC achieved the highest number of activated groups.
• The Threshold Impact: As $\beta$ (the threshold) increases, the gap between the proposed algorithms and simple heuristics (like Out-degree) widens significantly.
• Efficiency: CMC is not only effective but fast, with a runtime complexity of $O(nl+n+m)$, making it more scalable than simulation-heavy sampling methods.

Figure: CMC consistently leads in group activation across different seed set sizes (k).

Critical Analysis & Conclusion

Takeaway

The shift from IM to GIM is essential for "majority-rule" scenarios. The core insight is that connectivity $eq$ influence when groups have internal structures and thresholds. CMC successfully internalizes this by normalizing node contribution by the group's "resistance" ($|u_j|-H_{u_j}$).

Limitations & Future Work

• Heuristic Nature: CMC is a heuristic. While it performs well, it lacks the formal approximation guarantees found in the more complex (and slower) sandwich frameworks.
• Static Thresholds: The model assumes a fixed $\beta$. Future research could explore dynamic thresholds where a group's receptivity changes over time.

Overall, this work provides a practical toolkit for marketers and policymakers who need to influence collective entities rather than just scattered individuals.