Complex contagion and the weakness of long ties in social networks: Revisited

Diseases, information and rumors could spread fast in social networks exhibiting the small world property. In the diffusion of these "simple contagions", which can spread through a single contact, a small network diameter and the existence of weak ties in the network play important roles. Recent studies by sociolo- gists [Centola and Macy 2007] have also explored "complex contagions" in which multiple contacts are required for the spread of contagion. [Centola and Macy 2007] and [Romero et al. 2011] have shown that complex contagions exhibit different diffusion patterns than simple ones. In this paper, we study three small world models and provide rigorous analysis on the diffusion speed of a k-complex contagion, in which a node becomes active only when at least k of its neighbors are active. Diffusion of a complex contagion starts from a constant number of initial active nodes. We provide upper and lower bounds on the number of rounds it takes for the entire network to be activated. Our results show that compared to simple contagions, weak ties are not as effective in spreading complex contagions due to the lack of simultaneous active contacts; and the diffusion speed depends heavily on the the way weak ties are distributed in a network. We show that in Newman-Watts model with Θ(n) random edges added on top of a ring structure, the diffusion speed of a 2-complex contagion is ( 3√n) and O( 5pn4 log n) with high probability. In Kleinberg's small world model (in which Θ(n) random edges are added with a spatial distribution inversely proportional to the grid distance to the power of 2, on top of a 2-dimensional grid structure), the diffusion speed of a 2- complex contagion is O(log3.5 n) and (log n/ log log n) with high probability. We also show a similar result for Kleinberg's hierarchical network model, in which random edges are added with a spatial distribution on their distance in a tree hierarchy. In this model the diffusion is fast with high probability bounded by O(log n) and (log n/ log log n), when the number of random edges issued by each node is Θ(log2 n). We also generalize these results to k-complex contagions.