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

Golnaz Ghasemiesfeh, Roozbeh Ebrahimi, Jie Gao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationEC 2013 - Proceedings of the 14th ACM Conference on Electronic Commerce
Pages507-524
Number of pages18
StatePublished - 2013
Externally publishedYes
Event14th ACM Conference on Electronic Commerce, EC 2013 - Philadelphia, PA, United States
Duration: Jun 16 2013Jun 20 2013

Publication series

NameProceedings of the ACM Conference on Electronic Commerce

Conference

Conference14th ACM Conference on Electronic Commerce, EC 2013
Country/TerritoryUnited States
CityPhiladelphia, PA
Period6/16/136/20/13

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications

Keywords

  • Complex contagion
  • Computational social science
  • Diffusion
  • Social networks

Fingerprint

Dive into the research topics of 'Complex contagion and the weakness of long ties in social networks: Revisited'. Together they form a unique fingerprint.

Cite this