Small and other worlds: Global network structures from local processes

this research, and for the helpful comments of two reviewers. This research was conducted with support from the Australian Research Council, and was supported in part by grants from the NIH (R01-DA012831 and R01-HD041877). Using a simulation approach based on the Metropolis algorithm, we contrast broad global features of network structure – in particular, small world properties – with the local patterning that could generate the network. It is not difficult to infer local structures emerging from certain simple social processes but, as these localized patterns agglomerate, the global outcomes are often not apparent. In such cases, computational techniques are necessary because analytic solutions are simply not available. In this paper, we show how to simulate a distribution of Markov random graphs based on assumptions about simple local social processes. We examine the resulting global structures by comparison with an appropriate Bernoulli distribution of graphs and provide examples of various stochastic global “worlds ” that may result, including small worlds, long path worlds and dense non-clustered worlds with many four-cycles. In the light of these results we suggest a locally-specified social process that may result in small-world global properties. In examining the movement from structure to randomness, we show how parameter scaling relates to a phase transition occurring at a certain scaling (“temperature”) so that a regular structure “melts ” into a stochasticallybased counterpart. We provide examples of “frozen ” deterministic structures, including highly clustered “caveman ” graphs, bipartite structures, and global cyclic structures involving structurally equivalent groups. 1