Scheduling a Cascade with Opposing Influences
Preprint
Abstract
Adoption or rejection of ideas, products, and technologies in a society is often governed by simultaneous propagation of positive and negative influences. Consider a planner trying to introduce an idea in different parts of a society at different times. How should the planner design a schedule considering this fact that positive reaction to the idea in early areas has a positive impact on probability of success in later areas, whereas a flopped reaction has exactly the opposite impact? We generalize a well-known economic model which has been recently used by Chierichetti, Kleinberg, and Panconesi (ACM EC'12). In this model the reaction of each area is determined by its initial preference and the reaction of early areas. We generalize previous works by studying the problem when people in different areas have various behaviors. We first prove, independent of the planner's schedule, influences help (resp., hurt) the planner to propagate her idea if it is an appealing (resp., unappealing) idea. We also study the problem of designing the optimal non-adaptive spreading strategy. In the non-adaptive spreading strategy, the schedule is fixed at the beginning and is never changed. Whereas, in adaptive spreading strategy the planner decides about the next move based on the current state of the cascade. We demonstrate that it is hard to propose a non-adaptive spreading strategy in general. Nevertheless, we propose an algorithm to find the best non-adaptive spreading strategy when probabilities of different behaviors of people in various areas drawn i.i.d from an unknown distribution. Then, we consider the influence propagation phenomenon when the underlying influence network can be any arbitrary graph. We show it is $\#P$-complete to compute the expected number of adopters for a given spreading strategy.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships2013
- How to schedule a cascade in an arbitrary graph2012
- Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate2011
- Equilibrium Pricing with Positive Externalities (Extended Abstract)2010
- Efficient influence maximization in social networks2009
- Pricing Strategies for Viral Marketing on Social NetworksLecture Notes in Computer Science, 2009
- Optimal marketing strategies over social networks2008
- A Theory of Fads, Fashion, Custom, and Cultural Change as Informational CascadesJournal of Political Economy, 1992
- The Complexity of Reliability Computations in Planar and Acyclic GraphsSIAM Journal on Computing, 1986
- Threshold Models of Collective BehaviorAmerican Journal of Sociology, 1978