Cosin: Mastering Controllable Social Influence with ROI-Driven Distributed Optimization

TL;DR

Researchers have moved beyond fixed-budget Influence Maximization (IM) to propose Cosin, a framework that maximizes social influence spread within a controllable "hop-limit" while guaranteeing a specific Return on Investment (ROI). By ditching Monte Carlo simulations in favor of a theoretical multi-hop estimation framework and leveraging a distributed double-greedy algorithm, they achieved a 51x speedup on billion-scale networks like Twitter.

Background: The Budget Trap

In the classic IM problem, we assume we have $k$ dollars (or seeds) to spend. But in the real world, a CMO doesn't always know the "right" $k$. They care about the ROI—the ratio of people reached to the cost of acquisition. Existing SOTA methods (like IMM or SSA) often struggle when the marketing scope is restricted to a few "hops" or when the network size explodes, leading to massive memory overheads.

The "Cosin" Insight: Controllability and ROI

The authors identify two missing pieces in the social influence puzzle:

1. Hop Controllability: Influence shouldn't just "bleed" indefinitely; companies need to see how a product resonates within $t$ hops of a seed.
2. ROI as a Constraint: Instead of "spend $X$," the goal is "maximize reach such that every dollar spent brings in $Y$ amount of influence."

Solving the Overlap Problem

One of the core technical challenges is that when you add multiple seeds, their influence spheres overlap. Traditional "one-hop/two-hop" heuristics often double-count these users. The paper introduces a mathematical correction for influence increment (adding a user) and decrement (removing a user) to ensure theoretical accuracy without running 10,000 simulations.

Figure 1: Illustration of users activated exactly at the t-th hop, forming the basis for the theoretical estimation.

Methodology: Double Greed and Distributed Scalability

The authors propose SlightCosin, which employs a "Double Greedy" approach. It starts with an empty set $S$ and a full set $S^{\prime }$, narrowing the gap between them by calculating the marginal gain of either adding or removing a user.

To make this work at a "Twitter scale," they developed DisCosin.

• MapReduce Integration: They partition the users across mappers.
• Transactional Decisions: If the choice to add/remove a user is clear (based on upper/lower bounds of ROI), the mapper decides. If it's ambiguous, the user is passed to the next iteration (the "Uncertainty Set" $Z$).

Experimental Results: Beating the SOTA

The results on the LiveJournal and Twitter datasets are definitive.

• Scalability: While standard algorithms like IMM and SSA hit Out-of-Memory (OOM) errors at hop counts above 5 on Twitter, Cosin scaled gracefully up to 9 hops.
• Efficiency: DisCosin achieved 51x speedup compared to its serial version.
• Accuracy: The theoretical estimation closely matched the ground truth established by Monte Carlo simulations.

Figure 2: Influence spread comparison showing that Cosin maintains accuracy while significantly reducing computational overhead.

Critical Insight & Conclusion

The Cosin framework is more than just a faster IM algorithm; it’s a shift toward business-logic-aware AI. By treating ROI as a submodular constraint and replacing stochastic sampling with deterministic hop-based math, it bridges the gap between academic graph theory and practical viral marketing.

Limitations: The model assumes an Independent Cascade (IC) model for its primary derivations. While it claims equivalence to Linear Threshold (LT) models, the distributed calculation of overlap in LT models might introduce higher complexity in real-world messy data.

Future Work: Integrating this ROI-driven approach into "Competitive IM," where multiple companies fight for the same users, would be the next frontier for this research.