8 - An Introduction to Random Graphs, Dependence Graphs, and p*

Summary

We begin with a graph (or a directed graph), a single set of nodes N, and a set of lines or arcs ℒ. It is common to use this mathematical concept to represent a social network. We use the notation of Wasserman and Faust (1994), especially Chapters 13 and 15. There are extensions of these ideas to a wide range of social networks, including multiple relations, affiliation relations, valued relations, and social influence and selection situations (in which information on attributes of the nodes is available). Later chapters in this volume discuss such generalizations.

The model p* was first discussed by Frank and Strauss (1986), who termed it a distribution for a Markov random graph. Further developments, especially commentary on estimation of distribution parameters, were given by Strauss and Ikeda (1990). Wasserman and Pattison (1996) further elaborated this family of models, showing how a Markov parametric assumption provides just one of many possible sets of parameters. This family, with its variety and extensions, was named p*, a label by which it has come to be known. The parameters reflect structural concerns, which are assumed to govern the probabilistic nature of the underlying social and/or behavioral process.

The development of p* presented here is different from that found in Wasserman and Pattison (1996) and Anderson, Wasserman, and Crouch (1999), but similar to the presentation in Pattison and Wasserman (1999).