Decision cascades in social networks

December 22, 2014
Ripple across social networks. Image credit: Laurel Papworth. Credit: Creative Commons

How do people in a social network behave? How are opinions, decisions and behaviors of individuals influenced by their online networks? Can the application of math help answer these questions?

"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."

Explore further: How does innovation take hold in a community? Math modeling can provide clues

More information: How to Schedule a Cascade in an Arbitrary Graph, SIAM J. Comput., 43(6), 1906–1920 (Online publish date: December 16, 2014)., epubs.siam.org/doi/abs/10.1137/130936580

Related Stories

Uncovering complex network structures in nature

December 10, 2014

The global spread of Ebola is due to the complex interactions between individuals, societies, and transportation and trade networks. Understanding and building appropriate statistical and mathematical models of these interactions ...

Recommended for you

Predicting the future with the wisdom of crowds

June 23, 2017

Forecasters often overestimate how good they are at predicting geopolitical events—everything from who will become the next pope to who will win the next national election in Taiwan.

UN says world population will reach 9.8 billion in 2050

June 22, 2017

India's population is expected to surpass China's in about seven years and Nigeria is projected to overtake the United States and become the third most populous country in the world shortly before 2050, a U.N. report said ...

Authenticity key to landing a new job

June 22, 2017

At job interviews, relax and be yourself - if you're good, being yourself may be the best way to secure a job offer, according to a new study involving UCL researchers.

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.