Maximizing Influence in a Competitive Social Network: The Follower's Advantage

TL;DR

In the world of viral marketing, we often focus on the "first-mover advantage." This paper flips the script by asking: How can a second company effectively enter a market already occupied by a competitor? By modeling social networks as competitive arenas and proving the mathematical property of submodularity, the authors show that a follower can use a greedy algorithm to outmaneuver a larger competitor with surgical precision.

Problem & Motivation: Beyond the Single-Company Vacuum

Classic viral marketing models (like those by Kempe et al.) assume you are the only one trying to influence the world. But real markets are battlefields. Think Sony PlayStation vs. Nintendo Wii or VHS vs. Betamax.

When a competitor has already targeted "early adopters," the social network's landscape changes. Some nodes are already "poisoned" or occupied. The challenge is not just finding influential people, but finding people who can "steal" influence back or block the competitor’s growth. The authors define this as the Follower's Perspective: you know what the competitor did, and now you must decide your best response under a fixed budget.

Methodology: Two Ways to Compete

The paper introduces two distinct ways to model how influence "clashes" when two products meet:

1. The Distance-Based Model: This is inspired by facility location. A consumer looks at their social network and adopts the product of the "closest" early adopter. If two different products are equally close, the consumer chooses based on a probability proportional to the number of neighbors tied to each product.
2. The Wave Propagation Model: This is more step-by-step. Influence moves like a wave. In each time step, a node adopts the product used by its neighbors who were reached in the previous "wave." It’s a decentralized copycat mechanism.

Architecture of Influence

The researchers represent the network as a graph $G=(V,E)$. The core trick is treating the influence function $\sigma (I_A|I_B)$—the expected number of people adopting product A given competitor B's set—as a submodular function.

Figure 1: Comparison of adoption probabilities between the Distance-based and Wave Propagation models.

The "Greedy" Proof: Why It Works

The most significant technical contribution is the proof that these competitive models are monotone and submodular.

• Monotonicity: Adding more initial adopters to your set never hurts your final market share.
• Submodularity: The "diminishing returns" principle. Adding a specific influencer to a small set helps more than adding them to a large set.

Because of these properties, the authors prove that a Hill Climbing Algorithm (simply picking the best next node at every step) is guaranteed to get you within 63% (1 - 1/e) of the absolute best possible strategy, even though finding the perfect strategy is NP-hard.

Experimental Results: Industrial Espionage Pays Off

The authors tested their math on the HEP-Th coauthorship network. The results were striking:

• Algorithm vs. Heuristics: The greedy algorithm consistently crushed "High-Degree" (just picking people with many friends) and "Centrality" heuristics.
• The Follower's Edge: If Company A (the follower) knows exactly who Company B (the leader) targeted, they can capture a massive share of the market even with a smaller budget.

Figure 3: Performance of different strategies in the Distance-based model.

In many simulations, the "High-Degree" heuristic was actually a better defense for the leader (Company B) than the greedy single-player algorithm. This suggests that the standard "best" way to spread influence is fragile to competition.

Critical Insight & Conclusion

This paper provides a rigorous mathematical framework for competitive viral marketing. It moves the field from "how do I spread an idea?" to "how do I win a war of ideas?"

Takeaway for Practitioners: Knowledge of the competitor is more valuable than a massive budget. By using submodular optimization, a follower can identify "bridge" nodes that block a competitor's expansion while accelerating their own.

Limitations: The models assume you have perfect knowledge of the competitor's initial targets ($I_B$). In the real world, this requires market intelligence or "industrial espionage." Future work should address "uncertainty" in the competitor's set.

Future Outlook: The next frontier is the Stackelberg Game—where the leader anticipates the follower's greedy response and chooses their nodes to be as "un-stealable" as possible.