Decision 'cascades' in social networks

'The way in which information, decisions, and behaviors spread through a network is a fundamental social phenomenon, and the past several decades have shown that it is a phenomenon that can be studied using rich mathematical models,' says Flavio Chierichetti who co-authored a paper that studies online behavior, published this month in the SIAM Journal on Computing. 'At one level, these processes have elements in common with biological contagion, which is also inherently based on a mechanism of spread through a network. But at another level, the processes are different -- the spread of behavior is based on individual decision-making, and as such, can exhibit richer and more complex behavior than the more direct mechanics of biological contagion.'

Along with co-authors Jon Kleinberg and Alessandro Panconesi, Chierichetti studies how people in social networks are often influenced by each other's decisions, resulting in a run of behaviors in which their choices become highly correlated, thus causing a cascade of decisions. The authors focus on the problem of ordering in a cascade with the end goal of maximizing the expected number of 'favorable' decisions. 'Often, cascading behavior in a social network is guided by an entity that wants to achieve a certain outcome,' says Alessandro Panconesi. 'For example, a company might be trying to guide the adoption of a product by word-of-mouth effects, or a political movement might be trying to guide the success of its message in a population.'

'As we develop further insight into such questions, we can begin to map our understanding onto a wide range of phenomena in the world, including the formation of opinions, the adoption of new products and technologies, and the evolution of new cultural norms,' Chierichetti adds. 'A challenging question, and one where we are only in the early stages, is to understand how the local properties of individual decisions translate to the global properties of a full cascade, as behavior spreads through the whole network.'

Cascades of this kind are sensitive to the order in which people make decisions. For instance, the consequences of some early decisions can be amplified due to the effect they have on the rest of the population.

'Our work began from the realization that an organization trying to guide the success of a cascade sometimes has an interesting source of leverage under its control -- the timing by which it introduces the cascade to different parts of the network,' explains Jon Kleinberg. 'Consider for example how a company can choose to roll out a product at different times in different geographic areas or to different markets.'

'To our surprise, the success of the cascade can sometimes be greatly affected by this choice of timing -- with the right timing strategy, the cascade can have a good likelihood of spreading very widely, while with the wrong strategy, it can have very little chance of going far,' Kleinberg continues. 'The mathematical and computational challenge for us was then to characterize the kinds of timing strategies that are most effective, and how these strategies depend on the structure of the network in which they're operating.'

Despite a great deal of research on the properties of decision cascades, including strategies developed for 'seeding' cascades with initial adopters and offering incentives at various times, not much is known about this timing aspect.

In this paper, the authors provide an algorithm for this timing or scheduling problem in cascades, adapted from a widely used framework in economic theory. An arbitrary graph is used to represent the underlying social network.

Using two types of consumers, each with a preference for one of two products, the model assumes that each consumer gets a specific payoff from using his or her preferred product as well as from using his or her non-preferred product; the payoff from the preferred product in each case being greater. The payoff for a product also increases with each additional user a product has, that is, a component that accounts for the advantage bestowed by greater numbers of users for a product. Thus the equation factors in both an individual user's preference as well as the popularity of the product within the network.

'Our work has identified these timing effects as an important potential strategy for catalyzing a cascade. But our analyses work with a relatively streamlined model of individual decision-making,' Panconesi says. 'It would be very interesting to think about how our results could be extended to handle richer models of behavior at the individual level. And with richer models, it would also be interesting to look at datasets of product adoption over time, to see if we can identify cases in which an effective timing strategy was used, and to extract general principles from this kind of data.'