Given a set of species V, let us construct a food web by assigning interactions (links) randomly to species (nodes), but with equal probability p. Species will therefore have equal numbers of interactions on average. The probability that a species can be found with r links, and therefore be of degree r, is given by the binomial probability
If we assume that the number of species is far greater than the number of links per species, that is |V|>>r, then the above formula may be re-written as
where z is the average number of links per species, or the coordination number of the graph. The probability density function P(r) is a Poisson distribution, with mean z. Such graphs are known as Erdös-Renyi graphs and possess many interesting properties. While Erdös-Renyi random graphs rarely describe real-world food webs (that is, species in a community do not have on average the same number of interactions; see below), they prove useful in demonstrating certain concepts.
The link distribution P(r) describes, for a set of nodes V, an entire ensemble of graphs. For example, the graphs illustrated in Figure 2A are both realizations of graphs with p = 0.2, and |E| = 5. No two realizations of graphs based on the same link distributions need be the same in detail, but they will have the same properties on average. The entire set of graphs based on a given set of parameters is the ensemble, and ensemble properties are usually written in angled brackets as <X>. The ensemble number of links per node in our two graphs is therefore <2>. It is also interesting to note that the two graphs are in fact identical if one ignores the labeling of the nodes. The vertex arrangements differ, but the graphs themselves are identical, bearing exactly the same information. Identical graphs are said to be isomorphic. Recognizing graph isomorphism allows us to distinguish between the properties of a graph, and any particular depiction of that graph, whether by illustration or adjacency matrix. Determination, however, of whether two finite graph depictions are isomorphic becomes increasingly difficult as the size (|V| and |E|) of the graph increases. In fact, no formulaic solution exists to the problem, it is believed to be NP-hard or NP-complete, and it is usually tackled with algorithmic computational approaches of varying efficiencies. Are the two graphs in Figure 2B isomorphic? The answer is yes, but I will leave that demonstration as an exercise for the reader! (The figure is borrowed from Wikipedia’s entry on isomorphic graphs)