Mitigating Overexposure in Viral Marketing

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

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.

Introduction: The Risk of Overexposure

In the field of influence maximization, the prevailing goal is typically to select a small set of "seed" users to initiate a word-of-mouth cascade that maximizes reach. However, this approach often ignores the risk of overexposure. Empirical evidence, such as the "Groupon effect" on Yelp ratings or the decline in average ratings for niche books that win mainstream awards, suggests that reaching an unreceptive audience can damage a brand's reputation.

A social network with potential adopters (blue) and critics (red).

This paper addresses this gap by modeling cascades where reaching a "hater" incurs a concrete negative cost. The objective shifts from maximizing reach to maximizing a net payoff: the benefit of adopters minus the cost of rejecters.

The Theoretical Model

We propose a model where a product's quality is represented by a parameter $\phi$. Each agent $i$ in a social network has a criticality threshold $\theta_i$.

  • Acceptance: If $\phi \geq \theta_i$, the agent accepts the product, providing a positive payoff $p$ and continuing the cascade to neighbors.
  • Rejection: If $\phi < \theta_i$, the agent rejects the product, providing a negative payoff $-q$ and terminating that branch of the cascade.

The goal is to select a seed set to maximize the total payoff: $p \times (\text{total adopters}) - q \times (\text{total rejecters})$.

Algorithmic Solutions

The paper provides two main algorithmic results based on the seeding constraints:

  1. Unbudgeted Optimization: When a firm can seed any number of nodes, the problem is solvable in polynomial time. By mapping the social network onto a flow network, the optimal strategy is found using min-cut/max-flow techniques. This approach identifies the optimal clusters to activate while minimizing the "cost" of the boundary critics.
Transformation of the social network into a flow network for optimization.
  1. Budgeted Complexity: If the firm is limited to seeding at most $k$ nodes, the problem becomes NP-hard. This is proven via a reduction from the Clique problem, as the payoff function lacks submodularity, making standard greedy approximations ineffective.

Experimental Results and Insights

The model was evaluated using real-world network topologies from the SNAP project, including an email network (986 nodes) and a text message network (1,899 nodes).

Key Findings: * Strategic Restraint: The optimal strategy often involves not seeding certain users who would like the product, simply because they might pass it on to a large group of critics. This quantifies the value of avoiding the "Groupon effect." * Non-Monotonicity of Quality: Interestingly, increasing product quality $\phi$ does not always increase payoff. A "better" product can trigger a massive cascade into a highly critical network segment, leading to a net reputational loss. * Efficiency: The min-cut algorithm is highly efficient, computing optimal strategies for thousands of nodes in under 0.06 seconds.

Conclusion and Future Work

This research highlights that "going viral" is not a universal good. By treating the network as a collection of adopter clusters bounded by critics, firms can strategically manage reputational risk.

Future work could address current limitations, such as the assumption of deterministic thresholds and simple contagion. Exploring "complex" contagions—where multiple recommendations are required for adoption—and dynamic networks where links change based on experience would further refine the model's practical applicability.

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