CISM: Strategizing for Competitive Viral Marketing in Social Networks

TL;DR

In a world where Apple and Samsung compete for the same users, how does a "follower" company select seeds to maximize influence? This paper proposes CISM (Competitive Influence Spread Model), leveraging the concept of "possible graphs" to bypass #P-hard complexity and the CELF algorithm to achieve high-efficiency seed selection with a guaranteed (1 - 1/e) approximation of the optimal spread.

Background & Motivation: The Reality of Competition

Traditional research into Influence Maximization (IM) focuses on the "First Mover" advantage—identifying $k$ nodes to trigger the largest possible cascade. However, in reality, markets are rarely empty. When you launch a campaign, a competitor’s "Product B" might already be spreading.

The authors identify two critical gaps in prior work:

1. Computational Hardness: Calculating expected influence in the Independent Cascade Model (ICM) is #P-hard due to the nature of probability paths.
2. Competitive Dynamics: Most models don't account for the "collision" of two different information cascades in a discrete-time environment.

Methodology: Possible Graphs and The CISM Framework

1. From Probabilities to Possible Graphs

To solve the #P-hard challenge, the authors utilize the Possible Graph approach. In a social network $G=(V,E,P)$, every edge exists as a "live-edge" with probability $P$. By generating a set of representative deterministic "possible graphs," we can use simple Breadth-First Search (BFS) to calculate influence, which is significantly faster.

2. The Competitive Influence Spread Model (CISM)

CISM introduces a set of rules for "node capture" when two products compete:

• A-activated and B-activated seeds start the process.
• At each time step $t+1$, an inactive neighbor $v$ is checked.
• The Tie-Breaking Rule: If both Product A and Product B attempt to activate $v$ in the same step, the model grants activation to Product A (the user-controlled product). This specific design ensures that the objective function remains submodular, allowing for greedy optimization.

Figure: The activation logic of the CISM framework.

3. Acceleration via CELF

While the Greedy algorithm is effective, its $O(RKnm)$ complexity is too slow for large networks. The authors employ the CELF (Cost-Effective Lazy Forward) algorithm. CELF exploits the submodularity property (diminishing marginal returns) to skip redundant evaluations of nodes that couldn't possibly be the "best" in a current iteration.

Experimental Validation

The authors tested CISM on four datasets: NetHEPT, Ca-GrQc, p2p-Gnutella08, and Wiki-Vote.

Efficiency and Spread

The results confirm that the CELF-based CISM consistently outperforms:

• Max-Degree: Which often fails because high-degree nodes tend to cluster together, leading to "wasted" overlapping influence.
• Random: A baseline that lacks any strategic targeting.

Figure: Comparison of seed selection heuristics across multiple datasets.

Another key finding is the Influence/Ratio relationship. As the competitor's seed set ($|I_B|$) increases relative to your own ($|I_A|$), the marginal utility of your seeds drops, highlighting the "crowded market" effect.

Figure: The impact of $|I_B|/|I_A|$ ratio on the final activated node count.

Critical Insight & Conclusion

This paper provides a robust bridge between theoretical submodularity and the practical need for competitive marketing tools. By simplifying the stochastic nature of networks into a finite set of "possible worlds," the authors make competitive targeting computationally feasible.

Limitations: While CELF is fast, it still struggles with truly massive graphs (millions of edges). Future work must look toward asynchronous spread—where Product B might have a massive head start in time—and influence quality, where not all "activations" result in equal value.

For the practitioner, the takeaway is clear: when competing in social networks, don't just look for high-degree nodes. Use submodular optimization to find seeds that provide the maximum unique coverage in the presence of existing competition.