Complex contagions in Kleinberg's small world model

Roozbeh Ebrahimi, Jie Gao, Golnaz Ghasemiesfeh, Grant Schoenebecky

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

10 Scopus citations


Complex contagions describe diffusion of behaviors in a social network in settings where spreading requires influence by two or more neighbors. In a k-complex contagion, a cluster of nodes are initially infected, and additional nodes become infected in the next round if they have at least k already infected neighbors. It has been argued that complex contagions better model behavioral changes such as adoption of new beliefs, fashion trends or expensive technology innovations. This has motivated rigorous understanding of spreading of complex contagions in social networks. Despite simple contagions (k = 1) that spread fast in all small world graphs, how complex contagions spread is much less understood. Previous work [11] analyzes complex contagions in Kleinberg's small world model [14] where edges are randomly added according to a spatial distribution (with exponent γ) on top of a two dimensional grid structure. It has been shown in [11] that the speed of complex contagions differs exponentially when γ = 0 compared to when γ = 2. In this paper, we fully characterize the entire parameter space of γ except at one point, and provide upper and lower bounds for the speed of k-complex contagions. We study two subtly different variants of Kleinberg's small world model and show that, with respect to complex contagions, they behave differently. For each model and each k ≥ 2, we show that there is an intermediate range of values, such that when γ takes any of these values, a k-complex contagion spreads quickly on the corresponding graph, in a polylogarithmic number of rounds. However, if γ is outside this range, then a k-complex contagion requires a polynomial number of rounds to spread to the entire network.

Original languageEnglish (US)
Title of host publicationITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery, Inc
Number of pages10
ISBN (Electronic)9781450333337
StatePublished - Jan 11 2015
Externally publishedYes
Event6th Conference on Innovations in Theoretical Computer Science, ITCS 2015 - Rehovot, Israel
Duration: Jan 11 2015Jan 13 2015

Publication series

NameITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science


Other6th Conference on Innovations in Theoretical Computer Science, ITCS 2015

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics


  • Complex contagion
  • Kleinberg's small world model
  • Social networks


Dive into the research topics of 'Complex contagions in Kleinberg's small world model'. Together they form a unique fingerprint.

Cite this