# Rapid innovation diffusion in social networks

See allHide authors and affiliations

Edited by Brian Skyrms, University of California, Irvine, CA, and approved May 2, 2014 (received for review February 12, 2014)

## Abstract

Social and technological innovations often spread through social networks as people respond to what their neighbors are doing. Previous research has identified specific network structures, such as local clustering, that promote rapid diffusion. Here we derive bounds that are independent of network structure and size, such that diffusion is fast whenever the payoff gain from the innovation is sufficiently high and the agents’ responses are sufficiently noisy. We also provide a simple method for computing an upper bound on the expected time it takes for the innovation to become established in any finite network. For example, if agents choose log-linear responses to what their neighbors are doing, it takes on average less than 80 revision periods for the innovation to diffuse widely in any network, provided that the error rate is at least 5% and the payoff gain (relative to the status quo) is at least 150%. Qualitatively similar results hold for other smoothed best-response functions and populations that experience heterogeneous payoff shocks.

## Local Interaction Topology and Fast Diffusion

New ideas and ways of doing things often spread through social networks. People tend to adopt an innovation with increasing likelihood, depending on the proportion of their friends and neighbors who have adopted it. The innovation in question might be a technological advance such as a new piece of software, a medical drug (1), or a new hybrid seed (2). Or it might represent a social practice, such as contraception (3), a novel form of employment contract (4), or a group behavior such as binge drinking (5).

In recent years such diffusion models have been extensively studied from both a theoretical and an empirical standpoint. Some authors have highlighted the importance of the payoff gains from the innovation: Larger gains lead to faster adoption (2, 6). Others have pointed to the role that the network topology plays in the rate at which an innovation spreads (6⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓–19).

A key finding of this literature is that the amount of local clustering has a significant effect on the speed with which the innovation spreads. Fig. 1 presents three examples of simple networks that differ in the amount of local clustering. Fig. 1*A* shows a randomly generated network in which the neighborhoods of nearby agents have relatively little overlap. In such a network the expected waiting time until the innovation spreads grows exponentially in the network size unless the payoff gains from the innovation are very large (11, 18). Fig. 1*B* is a ring in which agents are connected to nearby agents. In this case the expected waiting time until the innovation becomes widely adopted is bounded independently of the network size (20). The intuition for this result is that the innovation gains an initial foothold relatively quickly within small groups of adjacent agents on the ring, and it then maintains its hold even when those outside the group have not yet adopted. Thus, the innovation tends to diffuse quite rapidly as it gains independent footholds among many groups scattered across the network. A similar logic applies to the lattice in Fig. 1*C*; in this case the local footholds consist of squares or rectangles of agents.

The contribution of this paper is to show that innovations can in fact spread quite rapidly in any finite network (as long as it does not have isolated vertices). The methods we use to establish our results are quite different from those in the prior networks literature, many of which rely on the “independent footholds” argument outlined above. Instead we take our inspiration from another branch of the learning literature, namely the analysis of dynamics when agents choose noisy best responses to samples drawn at random from the whole population. If the population is large, such a process can be well approximated by a deterministic (mean-field) dynamical system (14, 21⇓⇓⇓–25).

This setup is different from network models, in which agents choose noisy best responses to a fixed set of neighbors. To see the distinction, consider the situation where agents can coordinate on one of two actions: *A* (the innovation) or *B* (the status quo). Assume for the moment that they choose pure (instead of noisy) best responses to the actions of their neighbors. Such a game will typically have a vast number of heterogeneous equilibria whose structure depends on the fine details of the network topology. By contrast, in a global interaction model with sampling there will typically be just three equilibria, two of which are homogeneous and stable and the other one heterogeneous and unstable.

Now consider a (possibly noisy) best-response process and an unboundedly large number of agents who interact globally. The expected motion can be represented by a deterministic, continuous-time dynamic of the form *A* at time *t*, and

Of particular interest is the case where there is a single rest point and it lies above the halfway mark (0.5, 0.5) (red dashed curve in Fig. 2). [In almost any normal form game with the logit response function, for sufficiently large noise levels there is a unique rest point (a quantile equilibrium) (26). In the case when agents best respond to random samples, if there exists a *k* is a suitably chosen sample size), then the dynamics have a unique stable rest point (21, 24).] In this case the process moves from the initial state (all *B*) to a majority playing *A* in a bounded length of time. In an earlier paper we examined the implications of this observation for the logit best-response function (25). The main result in that paper is that, if the payoff gain from the innovation and/or the noise level is sufficiently large, then there is a unique rest point lying above (0.5, 0.5) and the expected waiting time until a majority of the agents choose *A* is bounded above independently of the population size; moreover, we give an explicit estimate of the expected waiting time. However, this argument depends crucially on the assumption that the agents interact globally, which ensures that the expected dynamics have the simple form shown in Fig. 2. This allows one to use standard stochastic approximation techniques to estimate the waiting time as a function of the payoffs, noise level, and sample size. In a network setting, by contrast, the underlying state space is vastly more complex and generally the unperturbed process will possess a large number of rest points, each with a different stochastic potential. Thus, the approximation techniques from our earlier paper do not apply to this case.

The contribution of the present paper is to show that, despite the complications introduced by the network setting, we can derive an upper bound on the rate of diffusion that holds uniformly for all networks provided that payoff gain from the innovation is sufficiently high and the noise level is not too low. These results are established using martingale arguments rather than the stochastic approximation methods that are common in the prior literature. The bound we establish is easy to compute, given the shape of the stochastic response function. Thus, our approach provides a practical estimation method that can in principle be applied to empirical data.

We emphasize that our results do not imply that network topology does not matter at all. Indeed, the diffusion rate will be faster than the upper bound that we establish, for classes of networks identified by previous research (14, 27). Thus, our results are particularly useful in situations where the exact topology of the network is not known or is changing over time.

The remainder of the paper is organized as follows. *The Local Interaction Model* introduces the adoption model with local interactions. In *Topology-Free Fast Diffusion in Regular Networks* we establish the main results for regular networks, and in *General Networks* we extend the arguments. In *Smooth Stochastic Best-Response Functions* we show that the results are robust for a large family of stochastic best-response functions other than the logit. We also show that the results can be interpreted in terms of payoff heterogeneity instead of noisy best responses.

## The Local Interaction Model

The model is expressed in terms of a stochastic process denoted *α*, the noise level *β*, and the interaction graph (or network) *G*. Consider a population of *N* agents numbered from 1 to *N* linked by an undirected graph *G*. We assume throughout this paper that each agent is connected to at least one other agent; i.e., the graph *G* does not have isolated nodes. Each agent chooses one of two available actions, *A* and *B*. Interaction is given by a symmetric 2 × 2 coordination game with payoff matrix

An important special case is when interaction is given by a pure coordination game with payoff matrix*B* as the “status quo” and of *A* as the “innovation.” The term

Payoffs are as follows. At the start of each time period every pair of agents linked by an edge interact once and they receive the one-shot payoffs from the game defined in [**1**]. Thus, each agent’s payoff in a given period is the sum of the payoffs from his pairwise interactions in that period. Note that players with a high number of connections will, *ceteris paribus*, have higher payoffs per period. Formally, let *i*’s payoff from interacting with *j*, when *i* plays *j* plays *i*’s neighbors, the total payoff for *i* from playing

We posit the following revision process. At times *G*. Assume that a fraction *x* of agent *i*’s neighbors are playing *A*; then *i* chooses a noisy best response given by the logit model,*f* on *A*. This is called the initial error rate. Both

Embedded in the above formulation is the assumption that the error rate depends only on the proportion of an agent’s neighbors playing *A* or *B* and it does not depend on the number of neighbors, that is, on the agent’s degree. In *Smooth Stochastic Best-Response Functions* we show that this follows naturally if we assume that in each period each agent experiences an idiosyncratic shock that affects his realized payoffs from all interactions during that period. The logit is one of the most commonly used models of this type (7, 8, 31⇓–33). The key feature of logit for our results is that the probability of not choosing the best response action decreases smoothly as a function of the payoff difference between the two choices. In *Smooth Stochastic Best-Response Functions* we show that the main result in this paper remains true for a large family of smooth stochastic response functions that are qualitatively similar to the logit. The stochastic response functions we consider emerge in a setting where agents myopically best respond to the actions of their neighbors, and payoffs from playing each action are subject to random shocks. (The response functions can also be viewed as a primitive element of the model that can be estimated directly from empirical data.)

The above revision process fully describes the stochastic process *i* plays *A* at time *t*, and *-B* state, namely

We now turn to the issue of speed of diffusion, measured in terms of the expected time until a majority of the population adopts action *A*. Formally, define the random hitting time*p* for the first time. The method of analysis in this paper can be extended in a straightforward way to treat this case.

Fast diffusion is defined as follows.

##### Definition 1:

Given a family *A* under process *S* independently of *G*; that is,

When the above conditions are satisfied, we say that

## Topology-Free Fast Diffusion in Regular Networks

In this section we establish our first result on sufficient conditions for fast diffusion in *d*-regular networks, and we provide an upper bound on the expected waiting time for a majority of the population to adopt. In the next section we show how to extend these arguments to general networks.

### Fast Diffusion in Regular Networks.

To find sufficient conditions for fast diffusion, we begin by lower bounding the expected change in the adoption rate in any state where adopters constitute a weak minority.

A graph *G* is *d* regular if every node in *G* has exactly *d* neighbors. Throughout this section, *d*-regular graphs. Fix a payoff gain *k* neighbors currently playing *A*.

The expected next period adoption of an agent *i* who has *k* neighbors currently playing *A* is**2**] from below, because this provides a lower bound on the expected change in the adoption rate for all configurations that have a minority of adopters. We begin by expressing *i*’s neighbors who have adopted the innovation. Let *i*. We can then write

We now apply Jensen’s inequality for the convex function **2**], we obtain*d*-regular graphs, as the following result shows. (The entire argument can be adapted to estimate the waiting time until a proportion

### Theorem 1.

*There exist uniform lower bounds on the payoff gain and the noise level such that the expected waiting time until a majority of agents play A is bounded for all regular graphs of degree at least one, irrespective of the number of agents. Concretely*, *displays fast diffusion whenever* *and* *Furthermore*, *given any* *displays fast diffusion whenever*

Prior work in the literature on fast diffusion in evolutionary models has focused mainly on the topological properties of the graphs in the family *Theorem 1* establishes topology-free bounds that guarantee fast diffusion for the entire family of *d*-regular graphs.

##### Proof:

The proof proceeds in two steps. First, we show that the expected change in the adoption rate is strictly positive whenever the adoption rate is at most

Fix some *Lemma 1* provides a positive lower bound for **3**] that the expected change in the adoption rate is strictly positive for any state such that

### Lemma 1.

*Let* *then* *for all*

##### Proof:

Because *f* is first convex and then concave, there exists *Lemma 1*.

■

The following claim provides explicit conditions that ensure that

### Claim 1.

*If* *then* *It follows that when* *the expected change in the adoption rate is positive in any state with*

The *Proof* of *Claim 1* relies on elementary calculus, using the logit formula, and can be found in *SI Text*.

We now turn to the second step in the *Proof*, namely that the expected waiting time to reach a majority of adopters is bounded for the family

We already know that for any *Lemma 1* we know that

### Lemma 2.

*Assume that* *is positive. Then for any* *the expected waiting time until a majority of the population adopts the innovation satisfies**Lemma 2* can be found in *SI Text*. It is based on inequality [**4**] and a careful accounting of the worst-case expected waiting time to go from a state with adoption rate

### Upper Bound on the Expected Waiting Time.

We now show how to obtain a bound on the absolute magnitude of the waiting time for any regular graph, irrespective of size or degree, using a technique similar to one contained in the *Proof* of *Theorem 1*.

Fix the payoff gain *G* be a *d*-regular graph on *N* vertices. Given an adoption level **2**]. We want to lower-bound this quantity independently of *d*. To this effect, let *d**Lemma 1*.)

We can now apply *Lemma 2* to establish a uniform upper bound on the expected waiting time, for any *d* and any *d*-regular graph (of any size), in terms of the shape of the function *G* we have

## General Networks

In this section we show how our framework can be applied to more general families of graphs. We derive a similar result to *Theorem 1*, but the proof is more complex and relies on stopping time results in the theory of martingales. Consider a finite graph *G* and let *i*. We assume that *i*; i.e., there are no isolated nodes. Denote the average degree in the graph by *G* (14, 23). In particular, adopters with higher degrees are weighted more heavily because they are more “visible” to other players. Note that the adoption rate *G* is regular.

The definitions of the expected waiting time *The Local Interaction Model* extend naturally to the adoption rate measure *G*. Note that the analysis that follows carries through if we define fast diffusion relative to a threshold

We begin by considering graphs with degrees bounded above by some integer

Choose some individual *i* and let *i*’s neighbors at time *t*. The expected change in *i*’s adoption rate is**6**] implies that*a fortiori* so is **5**], we obtain

### Proposition 1.

*and* *for*

##### Proof:

The intuition for the first statement is that when *A* whenever at least one neighbor plays *A*. Formally, for *Proposition 1* follow from *Claim 1* in the *Proof* of *Theorem 1*.

■

To study the family of all graphs, we can consider the limit as *D* tends to infinity. We claim that

The next result extends *Theorem 1* to the family of all graphs. It establishes the existence of a payoff threshold for fast diffusion, as well as an absolute bound on the expected waiting time.

### Theorem 2.

*Given a noise level* *if the payoff gain* *exceeds the threshold* *then diffusion is fast for all graphs. Moreover, when* *for any graph the expected waiting time until the adoption rate is at least* *satisfies**Theorem 2* shows that for any graph the expected time until the adoption rate *Theorem 2* provides an explicit bound on the expected waiting time that is easily computed and has a simple geometric interpretation.

We can improve on the threshold *Theorem 2* if we restrict ourselves to graphs with degrees bounded by some number *D*. Specifically, for any integer *D*. Moreover, if

A notable feature of these results is that the bounds are topology-free: They do not depend on any of the network details. The only other result in the literature of this nature is proposition 4 in (34), which shows that *Proposition 1* shows that the bound

Fig. 5 plots the threshold *D*. Fig. 5 also includes the threshold

For each pair *D*, the term *Theorem 2*. The bounds apply to all finite graphs, irrespective of maximum degree or size. For example, when

##### Remark:

Note that the waiting time upper bound in *Theorem 2* cannot be lower than *f*, which implies that

The numbers in Table 1 are expressed in terms of revisions per capita. The actual rate at which individuals revise will depend on the particular situation that is being modeled. For example, consider a new communication technology that is twice as good as the old technology when used by two agents who communicate with each other. Suppose that people review their decision about which technology to use once a week and that they choose a best response 9 times out of 10 initially (when there are no adopters). The model predicts that the new technology will be widely adopted in less than 7 mo irrespective of the network topology.

##### Proof of Theorem 2:

Inequality [**7**] implies that for any *T* is a submartingale. Define the process **8**] we know that *T* is still a submartingale.

Doob’s optional stopping theorem says that if *T* satisfies *p* we have *Theorem 2*. Rewriting this result, we obtain

Noting that *Proof* of *Theorem 1* we use a different method to establish the stronger bound

■

##### Remark:

The analysis so far corresponds to a worst-case analysis over all graphs with degrees below a certain *D*. When the degree distribution is known, this information can be used in conjunction with identity [**6**] to derive a more precise payoff threshold for fast diffusion. To illustrate, suppose we are given a degree distribution *d*. To be specific let us consider the case where *P* is described by the truncated power law

Fig. 6 plots a numerically simulated upper bound on the threshold for fast diffusion for the truncated distribution

The estimated curve in Fig. 6 has a very similar shape to the curves in Fig. 5. In particular, fast diffusion is achieved when the noise level is 5% and the payoff gain is at least

## Smooth Stochastic Best-Response Functions

In this paper we have established the existence of a payoff gain threshold that ensures fast diffusion in networks. The bound is “topology-free” in the sense that it holds for all networks. In this section we show that our method for proving these results does not depend in any crucial way on the logit response function: Results similar to those of *Theorems 1* and *2* hold for a large family of response functions that are qualitatively similar to the logit and that arise from idiosyncratic payoff shocks.

Assume that at the start of each period each agent’s payoffs from playing *A* and *B* are perturbed by independent payoff shocks *i*’s payoff from an interaction with *j* when playing *i*’s neighbors, which has

We stress that the shocks

Suppose that *x* is the proportion of adopters (i.e., *A* players) in the neighborhood of a given agent *i* in a given period. Let *i* chooses *A* is

If the shocks are drawn from an extreme-value distribution of the form

Another natural example is given by normally distributed payoff shocks. If the shocks are normally distributed with mean zero and SE

In general, consider a family of densities *i*) *ii*) for any *iii*)

The first condition implies that

We are now in a position to extend *Theorem 2* to general families of response functions. Let *Theorem 2* to families of payoff shocks that satisfy conditions *i* and *ii*.

### Theorem 3.

*Assume that agents experience independent and identically distributed payoff shocks drawn from a density* *that satisfies conditions i–iii*. *For any noise level* *there exists a payoff threshold* *such that whenever* *diffusion is fast for all graphs*. *Moreover*, *if* *then for every graph G the expected waiting time until the adoption rate is at least* *is at most*

In *SI Text* we present a different characterization of response functions that are similar to the logit, in terms of error functions. A salient characteristic of the logit is that the probability of an error can be expressed as a decreasing function of the payoff difference between the two alternatives. The risk-dominant equilibrium remains stochastically stable for a large class of such response functions (30). We show that there is a one-to-one correspondence between decreasing, convex error functions and families of payoff disturbances. It follows that the main message of *Theorems 1* and *2* carries through for a general class of error functions.

## Conclusion

In this paper we have studied some of the factors that affect the speed of diffusion of innovations on social networks. The two main factors that we identify are the payoff gain of the innovation relative to the status quo and the amount of noise in the players’ response functions.

As has been noted by a number of authors, including Griliches in his classic study of hybrid corn (2), larger payoff gains tend to increase the speed with which an innovation spreads. This makes intuitive sense. A less obvious but equally important factor is the amount of noise or variability in the players’ behavior. This variability can be variously interpreted as errors, experimentation, or unobserved payoff shocks. Under all of these interpretations, greater variability tends to increase the speed at which an innovation spreads. The reason is that higher variability makes it easier to escape from the initial low equilibrium. A particularly interesting finding is that different combinations of variability and payoff gain determine a threshold above which diffusion is fast in a “strong” sense; namely, the expected diffusion time is uniformly bounded irrespective of population size and interaction structure. These results are robust to quite general parameterizations of the variability in the system. For the logit, which is commonly used in empirical work, the waiting time is bounded (and quite small absolutely) if the initial error rate is at least 5% and the payoff gain from the innovation is at least 83% relative to the status quo.

Unlike previous results, a central feature of our analysis is that the bounds on waiting time are topology-free. The results apply to all networks irrespective of size and structure. In addition, our method of analysis extends to families of graphs with restrictions on the degree distribution. The virtue of this approach is that it yields concrete predictions that are straightforward to compute even when the fine details of the network structure are unknown, which is arguably the case in many real-world applications. Moreover, in practice social networks are constantly in flux, which makes predictions that depend on the specific network topology quite problematic. We conjecture that our framework can be extended to settings where the network coevolves with players’ choices, as in refs. 40 and 41 for example, but this issue will be left for future work.

## Acknowledgments

We thank Glenn Ellison and participants in the 2014 Sackler Colloquium, the MIT theory workshop, and the 2013 Brown University Mini-Conference on Networks for constructive suggestions. This research was sponsored by the Office of Naval Research Grant N00014-09-1-0751 and the Air Force Office of Scientific Research Grant FA9550-09-1-0538.

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. Email: gek{at}mit.edu.

Author contributions: G.E.K. and H.P.Y. designed research, performed research, contributed new reagents/analytic tools, and wrote the paper.

This paper results from the Arthur M. Sackler Colloquium of the National Academy of Sciences, “In the Light of Evolution VIII: Darwinian Thinking in the Social Sciences,” held January 10–11, 2014, at the Arnold and Mabel Beckman Center of the National Academies of Sciences and Engineering in Irvine, CA. The complete program and audio files of most presentations are available on the NAS website at www.nasonline.org/ILE-Darwinian-Thinking.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1400842111/-/DCSupplemental.

## References

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵.
- Bala V,
- Goyal S

- ↵
- ↵
- ↵.
- Valente T

- ↵.
- Carrington PJ,
- Scott J,
- Wasserman S

- Valente T

- ↵.
- Morris S

- ↵.
- Watts DJ

- ↵
- ↵
- ↵.
- Vega-Redondo F

- ↵
- ↵.
- Jackson MO

- ↵.
- Montanari A,
- Saberi A

- ↵.
- Newton J,
- Angus S

- ↵
- ↵
- ↵
- ↵
- ↵.
- Oyama D,
- Sandholm W,
- Tercieux O

*Theor Econ*, in press. - ↵
- ↵
- ↵.
- Young H

- ↵
- ↵
- ↵
- ↵.
- McFadden DL

- ↵.
- Anderson S,
- De Palma A,
- Thisse J

- ↵.
- Brock WA,
- Durlauf SN

- ↵.
- Young H

- ↵
- ↵.
- Grimmett G,
- Stirzaker D

- ↵
- ↵.
- Barabási A-L,
- Albert R

- ↵
- ↵
- ↵.
- Staudigl M

## Citation Manager Formats

## Article Classifications

- Social Sciences
- Economic Sciences