Small and Other Worlds: Global Network Structures from Local Processes

Abstract

Using simulation, we contrast global network structures—in particular, small world properties—with the local patterning that generates the network. We show how to simulate Markov graph distributions based on assumptions about simple local social processes. We examine the resulting global structures against appropriate Bernoulli graph distributions and provide examples of stochastic global “worlds,” including small worlds, long path worlds, and nonclustered worlds with many four‐cycles. In light of these results we suggest a locally specified social process that produces small world properties. In examining movement from structure to randomness, parameter scaling produces a phase transition at a “temperature” where regular structures “melt” into stochastically based counterparts. We provide examples of “frozen” structures, including “caveman” graphs, bipartite structures, and cyclic structures.