Beyond Clicks: Maximizing Real Adoption Across Multi-layer Social Networks

TL;DR

Most viral marketing models assume that influencing a user is the same as winning them over. This paper challenges that by introducing Adoption Maximization in Multi-layer Social Networks. The authors propose the HMA algorithm, which uses a clever h-hop sampling strategy to find the most influential seeds across different platforms (like Twitter and Facebook) while accounting for the reality that users might not adopt even if they see the info.

The "Adoption Gap" in a Multi-Platform World

Classic Influence Maximization (IM) targets a single network and assumes "influenced = success." However, the modern reality is twofold:

1. Multi-layer Presence: We use multiple accounts (Twitter, YouTube, LinkedIn). Influencing someone on one doesn't automatically mean they’ll share it to all others.
2. Adoption Resistance: A user might retweet a product but personally dislike it or decide not to buy it. This is the Adoption Probability ($1-P_c^u$).

Existing models fail because they either ignore layers or assume users are "info-bots" that sync everything perfectly across accounts.

Methodology: The MAIC Model and MRRA Sampling

The authors define the Multi-layer Adopted Independent Cascade (MAIC) model. Here, a user entity $e_u$ has nodes across different layers. Activation happens through:

• Solid Edges: Influence within the same platform.
• Dashed (Sharing) Edges: The probability $P_{ij}^u$ that a user migrates information from Layer $i$ to Layer $j$.

Fig 1: The MAIC model showing intra-layer influence (solid) and cross-layer sharing (dashed).

To solve this NP-hard problem, the authors extend the Reverse Influence Sampling (RIS) framework. They create Multi-layer Reverse Reachable Adoption (MRRA) sets. Instead of just looking at reachability, the MRRA generation incorporates the adoption probability, ensuring that the selected seeds are optimized for final converts, not just "eyes on screen."

The Secret Sauce: H-hop Acceleration

The biggest bottleneck in IM is calculating the sample size $heta$. To get a strict theoretical guarantee, you need an estimate of the optimal solution ($OPT$). Traditional methods (like MAIMM) are slow because they estimate $OPT$ iteratively.

The HMA Algorithm uses a h-hop based approach. By looking only at the immediate neighborhood (e.g., $h=3$), it quickly calculates a lower bound for influence. Because influence typically decays as it travels further, this local view provides a "good enough" baseline to set the sampling threshold, cutting computation time by over 70%.

Performance Benchmarks

The researchers tested their approach on large-scale datasets like Wiki-talk (1.1M nodes).

1. Effectiveness

Both the baseline and the HMA algorithm produced nearly identical adoption sizes, proving that the h-hop heuristic doesn't sacrifice quality for speed. (a) Adoption size increases steadily with seed set size (k).

2. Efficiency

This is where HMA shines. By avoiding the expensive iterative estimation of $OPT$, HMA achieved a 3.5x speedup compared to the MAIMM baseline. (d) HMA demonstrates significantly lower response time across varying k values.

Critical Insight & Future Work

The core value of this work lies in its realistic constraints. By treating "sharing between accounts" as a probabilistic edge rather than a certainty, it mirrors actual human behavior.

Limitations: The model currently assumes the "Adoption Probability" is independent of the number of times a user is influenced. In reality, being "pestered" by the same info across five different platforms might either increase adoption (social proof) or decrease it (annoyance). Future models might explore this non-linear adoption reinforcement.

Conclusion

The HMA algorithm provides a scalable, mathematically grounded framework for viral marketing. It proves that you don't need to sample the entire universe to find the center—sometimes, looking just a few hops away is the fastest path to global influence.