• What is this stuff?

Roopnarine's Food Weblog

~ Ramblings and musings in evolutionary paleoecology

Roopnarine's Food Weblog

Tag Archives: graph

The Cuban coral reef food web

17 Thursday May 2012

Posted by proopnarine in Coral reefs, Visualization

≈ 1 Comment

Tags

biodiversity, coral reef, coral reef food web, food webs, graph, invertebrates and vertebrates, marine communities, networks, prey and predator, real world networks, sfdp

This is a rendering of the Cuban coral reef food web from our set that also includes the Cayman Islands and Jamaica. All the data will be made available very soon in an upcoming publication. This is a metanetwork, or guild-level web where nodes represent one or more species with indistinguishable prey and predator links. There is a total of 266 guilds (nodes) in the network with 3899 interactions (edges) between them. The guilds in turn encompass 860 species, including protists, macroalgae, seagrasses, invertebrates and vertebrates. Colour codes: red – primary producers; yellow – invertebrates and heterotrophic protists; magenta – vertebrates.

The web or network was rendered with Graphviz using the neato algorithm (though sfdp also produces very pleasing images). Total cpu time varied between 1-4 seconds depending on options and machine.

New paper – Networks, extinction and paleocommunity food webs

21 Thursday Oct 2010

Posted by proopnarine in CEG theory

≈ Leave a comment

Tags

connectance, extinction, food webs, graph, link distribution, metanetwork, Network theory, networks, nonlinear, paleo-food web, power law, probability, real world networks, Robustness, simulations, trophic guild

Roopnarine, P. D. 2010. Networks, extinction and paleocommunity food webs in J. Alroy and G. Hunt, eds., Quantitative Methods in Paleobiology, The Paleontological Society Papers, 16: 143-161. (available here).

The paper is part of a volume, Quantitative Methods in Paleobiology, sponsored by The Paleontological Society. Full details are available here. The volume is also available for sale. Purchase one and support the Society!

Species-level networks

01 Monday Mar 2010

Posted by proopnarine in CEG theory

≈ Leave a comment

Tags

food webs, graph, link distribution, metanetwork, networks, paleo-food web, paleontology, trophic species

The final step in food web construction is the generation of species-level networks (SLNs). A SLN is considered here a single potential pattern of community interactions in any given place at an instant of time, and may be constructed in two distinctly different ways. First, using empirical observations, one could construct the SLN of a community. This is typically the fashion in which SLNs are reconstructed for modern communities; workers observe and record the community’s trophic interactions. SLNs of this type are precise and without error, though usually taxonomically incomplete, and we cannot have similar confidence in their accuracies because of the sources of uncertainty described above. Capturing their variability requires repeated observations, which is possible under some circumstances. For example, there has been documentation of seasonal variation in food webs. Repeat observations are impossible for paleo-food webs. The best that can be done is to measure spatial or temporal variation in taxonomic composition. The latter of course could describe variability on only the longest of ecological timescales. Dunne et al. (2008) (see previous post) compiled SLNs of two Cambrian food webs derived from the Burgess Shale and Chenjiang lagerstatten, comprising 142 and 85 taxa respectively. The taxa in both these networks were subsequently aggregated into trophic species, 48 and 33 respectively, on the basis that species within the trophic species have identical consumers and resources. As argued above, it is impossible to validate this claim for fossil taxa. Trophic species-level links were ranked according to uncertainty in these networks, but there was no explicit attention paid to uncertainty at the level of species within the trophic species.

SLN derived from metanetwork in previous post

The CEG model takes an alternative approach to SLN reconstruction, generating multiple plausible SLNs from the metanetwork and hypothetical or underlying principles of food web networks as gleaned from modern food webs. This type of SLN generation requires a trophic in-link distribution for each guild. Recall that a trophic in-link distribution describes the number of prey per species within a guild. This number ranges from 1 (a heterotrophic species must prey upon at least 1 other species) up to the total species-richness of all guilds that are specified as prey of the guild in the metanetwork. SLN-generation requires initially that species within a guild be treated neutrally, that is, they have no distinguishing trophic properties. Stochastic draws from specific guild trophic link distributions then determine the number of prey to be assigned to each species. The prey species themselves are drawn randomly from the pool of prey guilds of the predatory species. The result is a directed graph or network in which each species in the community has been assigned prey, and many therefore also have predators (see figure). SLNs capture the uncertainty associated with the reconstruction of fossil food webs, and in fact any food web, in a manner in which static or unvarying trophic link determinations cannot. Repeated stochastic generation of SLNs accounts for the sources of uncertainty discussed earlier, namely uncertainty of the particular interactions of a species, and the temporal and spatial variability of a community type. Also, even though any two SLNs derived from any moderately complex metanetwork are unlikely to share the same exact topology (isomorphic), they are drawn from the same ensemble, as discussed earlier for Erdӧs-Renyi random graphs. Whether the argument can then be extended to claim that they will also have the same behavior on average, as with random graphs, is an interesting question, because the ensemble is the range of variation possible for a paleocommunity’s food web based on paleontological uncertainty. The next few posts will therefore deal with a description of the ensemble, and the ecological dynamics of the SLNs in an ensemble.

Food webs as networks

23 Tuesday Feb 2010

Posted by proopnarine in Graph theory, Network theory

≈ Leave a comment

Tags

connectance, food webs, graph, interaction strength, Network theory, networks, real world networks, Robustness

Perhaps the most obvious structural elements of real food webs that distinguishes them from the graphs presented earlier is directionality of the links. Links are trophic interactions, that is, predator-prey relationships, and describe the passage of energy from prey species to predators. They can also be used to describe the impact of predation on a prey species, recognizing that the relationship is an asymmetrical one between nodes. The “traditional” manner in which to depict this graphically is with arrows between nodes (Fig. A). Whereas the graphs illustrated so far have been undirected graphs, a food web is defined properly as a directed graph, or digraph. The asymmetry is also reflected by the adjacency matrix, which is no longer symmetric about the diagonal.

The most straightforward applications of Graph Theory to food web biology are analyses of the structure or topology of digraphs. Digraphs are often referred to as networks in modern usage, and the study of digraphs, especially those describing real-world networks such as the Internet or social networks, is described as Network Theory. The reader should be aware, however, that networks are technically graphs that are digraphs having weighted or parameterized links. A network therefore depicts a food web when it contains species interactions, the direction of those interactions, and some measure of the interactions, such as interaction strength. A digraph without measures or weights on the links is in reality a special case of a food web digraph, one in which all links are considered equivalent.

A very simple three species food web is illustrated in Fig. A. Species 1 (S1) is prey only (perhaps a primary producer), S2 is both a predator or consumer of S1 while being prey to S3, and S3 is the top consumer in the network. Alternative arrangements for three species are illustrated in Fig. B-D, including a simple food chain (Fig. B), a web where the top consumer is also cannibalistic (Fig. C), and a cycle among the three species (Fig. D). These networks bear only information about the existence and direction of interactions among species, but this information is important because structure always affects function (Strogatz, 2001). The basic network approach has proven useful as a means of capturing the complexity of food webs, deriving basic comparative properties such as connectance and link distributions, and assessing one type of robustness against perturbation.

Random graphs and food webs

20 Saturday Feb 2010

Posted by proopnarine in CEG theory, Graph theory

≈ 1 Comment

Tags

graph, link distribution, probability

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
p(r) = \binom{\vert V \vert}{r} p^{r}(1-p)^{\vert V\vert -1-r} = \frac{\vert V\vert !}{r! (\vert V\vert -r)!} p^{r}(1-p)^{\vert V\vert -1-r}
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
p(r)\approxeq e^{-p\vert V\vert} \frac{(p\vert V\vert)^{r}}{r!} = e^{-z}\frac{z^{r}}{r!} ,
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)

Graphs and food webs

11 Thursday Feb 2010

Posted by proopnarine in CEG theory, Graph theory, Network theory

≈ 1 Comment

Tags

food webs, graph, paleo-food web, real world networks

I’m currently working on another review/instructional paper, this one examining the relationship of paleo-food webs to graph and network theory (along with excursions into combinatorics and counting). Here is a draft of one of the sections. This is a draft! No references, and sketches of figures will be added to the post as they are completed.

GRAPHS

A food web is a summary of interspecific trophic interactions. A mathematical graph is the combination of two sets, commonly written G(V, E), where the elements of E are relationships among the elements of V. Both concepts may be expressed graphically as diagrams of relationships among species or elements, an exercise that makes clear the relationship between the real-world biological system and the abstract mathematical one. The area of mathematics dealing with graphs is known as Graph Theory, familiarity with which proves very useful in the exploration and analysis of not only food webs, but of any real-world system (biological and otherwise) that can be expressed as relationships or interactions among discrete entities. Examples of other systems include networks of genomic interactions, metabolic networks, and phylogenetic trees.

Examine the food webs illustrated in Figure 1. The circles represent species, and the links between them are interspecific interactions. Describing these systems mathematically as G(V,E), the elements of E are relationships among the elements of V. The elements of V are typically referred to as vertices or nodes, and their relationships, or the elements of E, are referred to as edges. Edges are written as pairs of vertices, for example \{v_{1},v_{2}\}, where v_{1} and v_{2} are vertices in G (that is, v_{1}\in V and v_{2}\in V). Species in the food web are therefore nodes, and trophic interactions or links are edges. The first web (Fig. 1A) is a system of non-interacting species 1, 2 and 3. It could function only if embedded within a larger system of species with which these species interacted, or if all three species were autotrophic. Such a graph where no vertices or nodes are connected (E is an empty set) is an unconnected graph, one with some edges is connected (Fig. 1B), while a graph with all vertices connected (Fig. 1C) is a complete graph. Any node to which another is linked is termed its neighbor. Note the alternative representation of a graph as an n by n binary adjacency matrix, where element v_{i}v_{j} equals one if an edge connects the two vertices, and zero otherwise.

The three graphs would obviously depict food webs with very different implications for the species involved. For example, the density of interactions increases as the number of edges, or |E|, increases. This density is often described simply by the connectance (C) of the graph, standardized as the ratio of the number of edges to the maximum number of edges possible. Each node or species could hypothetically interact with every other species, therefore the number of possible interactions is n(n-1). Note, however, that links would be counted twice, for example {1,2} and {2,1}, so we halve this number. Then
C = \frac{2 |E|}{n(n-1)} = \frac{2|E|}{n^{2}-n}
The connectances of Figures 1A-C are therefore zero, 0.333 and 1. We extend this by noting that species may sometimes interact with themselves trophically if individuals are true cannibals. This situation is illustrated in figures as loops, or unit diagonal entries in the adjacency matrix (Fig. 1D). We can now generalize by stating that the connectance of food webs expressed as graphs is measured as
C = |E|\left( n+ \frac{n(n-1)}{2}\right)^{-1} = \frac{2|E|}{n^{2}+n}
and the connectance of the complete food web in Fig. 1D is therefore 1.

In addition to the overall link density of the graph, or the number of interactions in the food web, we are also interested in the number of interactions per species. This number indicates how trophically specialized or generalized a species is, and is interesting from both evolutionary and ecological perspectives. For example, very specialized species may have stronger coevolutionary interactions with the species to which they are linked, and specialization itself may require temporally extended intervals of stability or high productivity to evolve. Generalized species, on the other hand, could be less susceptible to major perturbations if the intensities of their interactions are distributed broadly among their neighbors. The number of edges or links attached to a node is termed the degree of the node. The simplest cases are those where all nodes are of the same degree, for example Figs. 1A, 1C and 1D. The distribution of links within the graph, or the link distribution, is then single-valued, and may be described as a Dirac delta function or Kronecker’s delta. A slight generalization, where nodes have the same number of links on average, instead of precisely the same degree, leads to the significant development of random graphs and the eventual study of real-world networks.

Next up:Random graphs

Blog Stats

  • 66,357 hits

Categories

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 1,373 other followers

Copyright

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Blog at WordPress.com.

  • Follow Following
    • Roopnarine's Food Weblog
    • Join 1,373 other followers
    • Already have a WordPress.com account? Log in now.
    • Roopnarine's Food Weblog
    • Customize
    • Follow Following
    • Sign up
    • Log in
    • Report this content
    • View site in Reader
    • Manage subscriptions
    • Collapse this bar
 

Loading Comments...