Introduction
Traditional viral marketing strategies operate under a "more is better" philosophy. The objective is typically to maximize the reach of a campaign by identifying a "seed set" of influential users who can trigger the largest possible cascade of adoptions. However, this approach ignores a critical real-world risk: overexposure.
Empirical evidence from platforms like Yelp and Goodreads suggests that aggressive marketing to an unreceptive audience can backfire. For instance, products that receive prestigious awards or are featured in massive discount campaigns (like Groupon) often experience a "discontinuous drop" in average ratings. This occurs because the product reaches individuals whose preferences do not align with it, leading to negative reviews and reputational damage. This paper formalizes this trade-off and proposes algorithms to optimize marketing reach while avoiding hostile clusters.
The Overexposure Model
The authors introduce a model where each agent $i$ in a social network $G$ has a criticality parameter $\theta_i$, representing their threshold for liking a product. The product itself has an appeal $\phi$.
- Acceptance: If $\phi \ge \theta_i$, the agent accepts the product, yielding a positive payoff $p$, and propagates the information to their neighbors.
- Rejection: If $\phi < \theta_i$, the agent rejects the product, resulting in a negative payoff $-q$, and terminates the cascade.
This model captures the tension between growth and reputation. A firm must decide which users to seed to maximize the total payoff, knowing that a successful cascade might inadvertently "leak" into a cluster of critics.
Algorithmic Solutions
The Unbudgeted Case
When there is no limit on the number of initial seeds, the problem remains complex because seeding a "fan" might trigger a chain reaction that hits a large "critic" cluster. Surprisingly, the authors prove that the optimal seed set can be found in polynomial time. They map the network to a Minimum Cut problem in a flow network.
By constructing a flow network where edges represent potential cascades and nodes represent payoffs, the min-cut identifies the optimal set of clusters to activate while "paying" the minimum cost to avoid or absorb negative payoffs.
The Budgeted Case
In contrast, if the firm is restricted to seeding at most $k$ nodes, the problem becomes NP-complete. The authors demonstrate this through a reduction from the Clique problem, indicating that finding an optimal solution or even a high-quality approximation is computationally difficult for large networks.
Experimental Results
The model was evaluated using real-world network topologies from the Stanford Network Analysis Project (SNAP), specifically an Email Network (986 nodes) and a Text Message Network (1,899 nodes).
The results highlight several key phenomena:
- The Groupon Effect: As shown in the figures, the payoff function is non-monotonic. Increasing a product's appeal (e.g., lowering the price) can actually decrease the total payoff. This happens when a higher $\phi$ allows a cascade to bridge into a highly critical part of the network that was previously shielded by "barrier" nodes.
- Strategic Avoidance: The optimal strategy often involves deliberately not seeding certain positive-inclined users if they serve as bridges to large clusters of critics.
- Performance: The min-cut algorithm significantly outperformed naive baselines (such as seeding all nodes with positive individual payoffs) and proved to be highly efficient, computing optimal sets in under 0.1 seconds.
Conclusion
This research provides a theoretical foundation for understanding overexposure in social networks. By accounting for the negative payoffs of reaching the wrong audience, firms can design more surgical marketing campaigns. Future work may extend this model to include probabilistic spread, "complex contagion" thresholds, and dynamic reputational effects where negative reviews influence the product's appeal over time.
Summary updated