How to schedule a cascade in an arbitrary graph

When individuals in a social network make decisions that depend on what others have done earlier, there is the potential for a cascade to form - - a run of behaviors that are highly correlated. In an arbitrary network, the outcome of such a cascade can depend sensitively on the order in which nodes make their decisions, but to do date there has been very little investigation of how this dependence works, or how to choose an order to optimize various parameters of the cascade. Here we formulate the problem of ordering the nodes in a cascade to maximize the expected number of "favorable" decisions - those that support a given option. We provide an algorithm that ensures an expected linear number of favorable decisions in any graph, and we show that the performance bounds for our algorithm are essentially the best achievable assuming P ≠ NP. © 2012 ACM.