Title: Long ties accelerate noisy threshold-based contagions,
Abstract: Changes to network structure can substantially affect when and how widely new
ideas, products, and conventions are adopted. In models of biological
contagion, interventions that randomly rewire edges (making them "longer")
accelerate spread. However, there are other models relevant to social
contagion, such as those motivated by myopic best-response in games with
strategic complements, in which individual's behavior is described by a
threshold number of adopting neighbors above which adoption occurs (i.e.,
complex contagions). Recent work has argued that highly clustered, rather than
random, networks facilitate spread of these complex contagions. Here we show
that minor modifications of prior analyses, which make them more realistic,
reverse this result. The modification is that we allow very rarely below
threshold adoption, i.e., very rarely adoption occurs, where there is only one
adopting neighbor. To model the trade-off between long and short edges we
consider networks that are the union of cycle-power-$k$ graphs and random
graphs on $n$ nodes. We study how the time to global spread changes as we
replace the cycle edges with (random) long ties. Allowing adoptions below
threshold to occur with order $1/\sqrt{n}$ probability is enough to ensure that
random rewiring accelerates spread. Simulations illustrate the robustness of
these results to other commonly-posited models for noisy best-response
behavior. We then examine empirical social networks, where we find that
hypothetical interventions that (a) randomly rewire existing edges or (b) add
random edges reduce time to spread compared with the original network or
addition of "short", triad-closing edges, respectively. This substantially
revises conclusions about how interventions change the spread of behavior,
suggesting that those wanting to increase spread should induce formation of
long ties, rather than triad-closing ties.