Jigsaw percolation: What social networks can collaboratively solve a puzzle?

Abstract

We introduce a new kind of percolation on finite graphs called jigsaw percolation. This model attempts to capture networks of people who innovate by merging ideas and who solve problems by piecing together solutions. Each person in a social network has a unique piece of a jigsaw puzzle. Acquainted people with compatible puzzle pieces merge their puzzle pieces. More generally, groups of people with merged puzzle pieces merge if the groups know one another and have a pair of compatible puzzle pieces. The social network solves the puzzle if it eventually merges all the puzzle pieces. For an Erdős-Rényi social network with $n$ vertices and edge probability $p_n$, we define the critical value $p_c(n)$ for a connected puzzle graph to be the $p_n$ for which the chance of solving the puzzle equals $1/2$. We prove that for the $n$-cycle (ring) puzzle, $p_c(n)=\Theta (1/\log n)$, and for an arbitrary connected puzzle graph with bounded maximum degree, $p_c(n)=O(1/\log n)$ and $\omega (1/n^b)$ for any $b>0$. Surprisingly, with probability tending to 1 as the network size increases to infinity, social networks with a power-law degree distribution cannot solve any bounded-degree puzzle. This model suggests a mechanism for recent empirical claims that innovation increases with social density, and it might begin to show what social networks stifle creativity and what networks collectively innovate.

arXiv commentPublished at http://dx.doi.org/10.1214/14-AAP1041 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (10)

• The structure of scientific collaboration networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Evolution of the social network of scientific collaborations
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• The Web of Human Sexual Contacts
• The power of a good idea: quantitative modeling of the spread of ideas from epidemiological models
• Communities, Knowledge Creation, and Information Diffusion
• Local cluster aggregation models of explosive percolation
• The Interacting Branching Process as a Simple Model of Innovation
• Jigsaw Percolation on Erdos-Renyi Random Graphs

Cited by in corpus (7)

• Model of human collective decision-making in complex environments
• Bootstrap percolation on a graph with random and local connections
• Group formation on a small-world: experiment and modelling
• Analyzing resilience of interest-based social networks against node and link failures
• The sharp threshold for jigsaw percolation in random graphs
• Shotgun identification on groups
• Transitive closure in a polluted environment