Mitigating Overexposure in Viral Marketing

Rediet Abebe, Lada A. Adamic, Jon M. Kleinberg

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.

Mapping the unbudgeted seeding problem 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).

Payoff vs. product appeal (phi) for Email and Text networks, showing the non-monotonicity of the optimal strategy.

The results highlight several key phenomena:

  1. 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.
  2. Strategic Avoidance: The optimal strategy often involves deliberately not seeding certain positive-inclined users if they serve as bridges to large clusters of critics.
  3. 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

Abstract

In traditional models for word-of-mouth recommendations and viral marketing, the objective function has generally been based on reaching as many people as possible. However, a number of studies have shown that the indiscriminate spread of a product by word-of-mouth can result in overexposure, reaching people who evaluate it negatively. This can lead to an effect in which the over-promotion of a product can produce negative reputational effects, by reaching a part of the audience that is not receptive to it. How should one make use of social influence when there is a risk of overexposure? In this paper, we develop and analyze a theoretical model for this process; we show how it captures a number of the qualitative phenomena associated with overexposure, and for the main formulation of our model, we provide a polynomial-time algorithm to find the optimal marketing strategy. We also present simulations of the model on real network topologies, quantifying the extent to which our optimal strategies outperform natural baselines
BibTeX
@inproceedings{abebe2018mitigating,
  author = {Rediet Abebe and Lada A. Adamic and Jon M. Kleinberg},
  title = {{Mitigating Overexposure in Viral Marketing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11282},
}
Figure