“Small and Other Worlds: Global Network Structures from Local Processes,” G. Robins et al (2005)

The global structure of a network is a function of local decisions made by agents on the network. For instance, agents may have a propensity to form triads, where A and C have a greater propensity to be connected if A is already connected to B and B to C (this is called balance theory). Given local properties such as balance theory, what should we expect the global network to look like; for instance, what will be the average path length between any two agents? The standard random graph model, a Bernoulli graph, assigns a number p(ij) of a connection between any agents i and j, but clearly this does not allow any local effects beyond the dyad level. Robins and coauthors show how to use the simulate distributions of “Markovian random graphs” that allow for examination of the changes in the distribution of the global structure when, for instance, propensity for triads decreases. The Markovian graph distribution can then be compared using maximum likelihood techniques to a Bernoulli graph distribution in order to examine the size of the effects. The statistics in this paper are not terribly complicated; over the past five years, hypothesis testing on (inherently-correlated) network data has been a booming field of research.


%d bloggers like this: