Complex contagions in Kleinberg's small world model

DOI10.1145/2688073.2688110zbMATH Open1366.91121arXiv1408.2159OpenAlexW2126745852MaRDI QIDQ2989015FDOQ2989015

Authors:

Publication date: 19 May 2017

Published in: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Abstract: Complex contagions describe diffusion of behaviors in a social network in settings where spreading requires the 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~cite{Ghasemiesfeh:2013:CCW} analyzes complex contagions in Kleinberg's small world model~cite{kleinberg00small} where edges are randomly added according to a spatial distribution (with exponent $gamma$) on top of a two dimensional grid structure. It has been shown in~cite{Ghasemiesfeh:2013:CCW} that the speed of complex contagions differs exponentially when $gamma=0$ compared to when $gamma=2$. In this paper, we fully characterize the entire parameter space of $gamma$ 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 $kgeq2$, we show that there is an intermediate range of values, such that when $gamma$ takes any of these values, a $k$-complex contagion spreads quickly on the corresponding graph, in a polylogarithmic number of rounds. However, if $gamma$ is outside this range, then a $k$-complex contagion requires a polynomial number of rounds to spread to the entire network.

Full work available at URL: https://arxiv.org/abs/1408.2159

Recommendations

• The Routing of Complex Contagion in Kleinberg’s Small-World Networks
• Complex contagions on configuration model graphs with a power-law degree distribution
• Cascades and myopic routing in nonhomogeneous Kleinberg's small world model
• CONTAGION AND THE SPEED OF ADJUSTMENT IN SMALL WORLDS
• Contagion and coordination in random networks

zbMATH Keywords

social networkscomplex contagionKleinberg's small world model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cited In (8)

• The Routing of Complex Contagion in Kleinberg’s Small-World Networks
• Effects of inspections in small world social networks with different contagion rules
• Analysis of Contagion Maps on a Class of Networks That Are Spatially Embedded in a Torus
• Complex contagions with social reinforcement from different layers and neighbors
• Complex contagions on configuration model graphs with a power-law degree distribution
• Cascades and myopic routing in nonhomogeneous Kleinberg's small world model
• Think globally, act locally: on the optimal seeding for nonsubmodular influence maximization
• Accelerated information dissemination on networks with local and global edges

This page was built for publication: Complex contagions in Kleinberg's small world model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989015)