Beyond Spreading: Maximizing Matched Participants in Social Networks

TL;DR

Information viral spread is not the same as participation success. In activities like group-buying, users only participate if they can match with partners. This paper defines the Matched Participants Maximization (MPM) problem, proves its complexity (NP-hard), and provides efficient approximation algorithms (OP-MPM and SA-MPM) that solve the "matching gap" in social network promotion.

Motivation: The "Loneliness" of Viral Spread

Traditional Influence Maximization (IM) models prioritize reaching the maximum number of people. However, consider a "buy one, get one free" deal that requires two people to join. If a user receives the info but none of their matchable friends do, the spread is a failure.

The authors identify two real-world matching scenarios:

• Neighbor Matching (NM): You only pair with direct friends (e.g., going to a movie).
• Global Matching (GM): A platform matches you with any eligible stranger (e.g., Pinduoduo group buying).

Methodology: Bridging Influence and Matching

The research introduces the Interest-based Forwarding (IF) model. Unlike the Independent Cascade (IC) model which relies on edge probabilities, IF emphasizes that activation depends on a node's inherent interest probability $p_v$ once they receive information.

1. The MPM-NM Algorithm (Neighbor Matching)

The objective function for NM is submodular, allowing for a greedy solution with a $(1-1/e-ϵ)$ guarantee. The core innovation is the Matching Reachable Set (MRS).

• MRS Logic: Instead of heavy Monte Carlo simulations, it samples sets of nodes that could potentially form a matched pair based on shared traits (matching indices) and reachability.

2. The MPM-GM Algorithm (Global Matching)

The GM strategy is not submodular, making it much harder to optimize. The authors use a Sandwich Framework:

• Lower Bound: The NM result (since NM is a subset of GM).
• Upper Bound: Created by extending the graph with "virtual edges" between all nodes sharing the same matching index.
• The algorithm selects the best result between these bounds, providing a robust $\beta (1-1/e-ϵ)$ approximation.

Experiments & Results

The researchers tested their models on datasets including Flickr and Twitter.

Efficiency vs. Effectiveness

• Superior Accuracy: The proposed SA-MPM consistently yielded more final participants than traditional IM-IF models, proving that "widest spread" is often sub-optimal for group activities.
• Computational Speed: While a standard Greedy approach takes hours due to Monte Carlo simulations, the MRS-based algorithms run in seconds/minutes.

Graph: SA-MPM significantly outperforms Random and IM-IF baselines in Global Matching scenarios.

Critical Insight: Why Does This Matter?

The industry value of this paper lies in Product-Growth Alignment. Many social platforms currently optimize for "Shares" or "Views." This research provides a mathematical framework to optimize for "Conversions" in collaborative environments.

Limitations & Future Work

The current model assumes a static matching index. In reality, user interests and matching criteria (like location) might change over time. Future research could explore dynamic Matching Reachable Sets that evolve with the social context.

Conclusion

By integrating matching theory with social influence, the authors have bridged the gap between social information spread and actual participant conversion. Whether you are building the next group e-commerce giant or a localized social event app, the MRS-based approach offers a principled way to select seeds that don't just "talk," but actually "act" together.