M&M: Unlocking Cross-Platform Influence via Multi-Aligned Heterogeneous Social Networks

TL;DR

Modern social influence doesn't happen in a vacuum. Users jump between Twitter, Foursquare, and LinkedIn, carrying ideas across boundaries through "anchor accounts." This paper introduces the M&M model, the first framework to solve Influence Maximization (IM) across partially aligned heterogeneous networks. By extracting complex relations through meta-paths and extending the Linear Threshold (LT) model, M&M manages to outperform traditional single-network and multiplex strategies by over 100%.

The "Single Network" Fallacy and the Anchor User Insight

Most viral marketing research treats social networks as isolated islands. However, the authors observe two critical real-world phenomena:

1. Heterogeneity: Users don't just "follow"; they retweet, check-in, and list-share. Each is a different channel of influence.
2. Alignment: "Anchor users" bridge different platforms. Data from Twitter and Foursquare reveals that while 81.8% of anchor users repost activities across networks, they only share a small fraction of their total content. Simple network merging fails because it ignores this "leaky" propagation.

Methodology: MMNs and Meta-Paths

The core innovation lies in the Multi-aligned Multi-relational Networks (MMNs). The M&M model uses Social Meta-Paths to define how influence flows.

1. Extracting Multi-Relations

Instead of a simple directed graph, the authors define:

• Intra-network Meta-Paths: e.g., User -> Tweet -> Retweet -> User (Twitter) or User -> Location -> User (Foursquare).
• Inter-network Meta-Paths: e.g., User(Twitter) -> Anchor Link -> User(Foursquare).

2. The Diffusion Model: Extended Linear Threshold

Standard LT models are binary. M&M extends this by calculating "Diffusion Strengths" $(\varphi ,\psi )$ for every relation using the PathSim metric. It then aggregates these via a Logistic Function, ensuring that influence from multiple types of interactions is weighted realistically.

Fig 1: The AHI problem illustration - from raw heterogeneous networks (A) to the constructed MMN (B).

Guaranteed Efficiency: The M&M Greedy Algorithm

Influence maximization is NP-hard. However, the authors prove that their AHI influence function is both monotone and submodular. This is a powerful theoretical guarantee: it means a simple greedy algorithm (Algorithm 1) can achieve an approximation ratio of $(1-1/e)$ (roughly 63% of the optimal).

Experimental Battleground: Twitter vs. Foursquare

The authors tested M&M against several baselines, including LCI (multiplex network model) and Greedy (single heterogeneous network model).

Key Findings:

• Global vs. Local: Selecting seeds across both networks (M&M) consistently beat selecting from only one (M&M-F or M&M-T).
• The M&M Advantage: M&M outperformed the leading multiplex model (LCI) by 117% in user activation.
• Cross-Network Superiority: Even with limited anchor links (30% ratio), accounting for cross-network propagation yields better seed sets than ignoring those links entirely.

Fig 2: Comparison of influenced users under different seed set sizes (30% anchor ratio).

Critical Analysis & Conclusion

Takeaway

The AHI problem represents a shift from "network-centric" to "user-centric" influence modeling. By treating the user's presence across multiple platforms as a unified identity bridged by anchor links, M&M captures the true reach of viral marketing.

Limitations & Future Work

• Weight Sensitivity: The paper assumes equal weights (0.25) for all relations. In reality, a "follow" might be much more influential than a "shared location."
• Threshold Dynamics: User thresholds are sampled uniformly; incorporating real-world behavioral data could further refine the model.
• Scalability: The meta-path instance count grows exponentially; future work might explore graph embedding techniques to simplify the MMN structure without losing semantic richness.

In conclusion, M&M provides a mathematically rigorous and practically superior framework for navigating the complex web of modern social influence.