Random Graph Models

Social network analysis derives much of its quantitative rigor from graph theory, an area of mathematics that studies objects (nodes) and the relationships or connections between these nodes (edges). Graph theory can be used to understand the underlying structure of a social network, and one approach is by the use of random graph models. In this case, one creates a graph or set of graphs by randomly assigning the number of nodes within a graph and randomly assigning the edges connecting individual nodes. Random graph models can be used to generate new networks or modify pre-existing ones, and help researchers understand the underlying mechanisms that lead to specific properties of an observed social network.

Random graph models are useful because they provide node- or edge-level mechanisms that help explain properties one observes in the network. Such properties may include degree distributions, reciprocity, or clustering (e.g., the presence of different triads). By providing mechanisms for forming networks, random graph models also allow one to build null hypotheses and other tests to examine whether observed networks have emerged through the mechanisms described by various random graph models.

A basic example of a random graph model is the Erdös-Rényi model. In such a model, one is given a set of n nodes in a network, and each edge exists with a probability p. Each edge exists independently of other edges. The strength of the Erdös-Rényi model is that it is well understood in comparison to other random graph models. Since each edge exists independently of every other edge, the expected number of edges in a directed version of the graph is n(n−1)p, while it is 0.5n(n−1)p for an undirected graph. An interesting aspect of the model is that as one increases the probability of edges existing, the graphs generated tend to transition from ones with many disconnected parts to graphs comprised of one giant component.

In the context of social network analysis and modeling networks, a major weakness of this model is its inability to form complex subgraph structures. If one is modeling reciprocity (if a node A links to node B, then node B also tends to link to node A), triadic closure (if A links to B and B links to C, then A tends to link to C), or other phenomena, then one needs to adopt more complex modeling strategies. Furthermore, the degree distribution of such models tends to be unrealistic.

Due to the lack of realism of the model above, social network analysts tend to adopt more complicated models of network formation or generation. A popular model is based on preferential attachment mechanisms, which are based on the “rich get richer” phenomenon. When generating such a network, one adds a node to the network with m edges, and the probability that any [Page 736]one of the edges of this new node links to a given preexisting node is proportional to the degree of the preexisting node. As such, nodes with a high degree tend to obtain new connections more quickly than nodes with a low degree.

...