Shakespeare, Rome and Paul Revere — the networks

This blog has emphasized that phylogenetic networks are fundamentally different from other types of biological network. For most networks, the nodes and the edges are observed — the nodes represent objects (organisms, proteins, species, etc), and the edges represent known interactions between the objects (so that they are sometimes called interaction networks).

For phylogenetic networks, on the other hand, the leaf nodes are observed while most of the internal nodes are inferred (except perhaps in population studies) and all of the edges are inferred. These networks rarely make it into books with "biological networks" in the title.

That does not make interaction networks uninteresting, of course. Indeed, they can be an excellent way of summarizing complex data. Below, I illustrate three examples from the humanities, just to emphasize how different they are from phylogenetic networks.

The first example is from Martin Grandjean's blog. You can download the full-size network poster from there. What the networks show is the structure of Shakespeare’s tragedies — I have chosen the play Macbeath for illustration. Two characters are connected in each network every time they appear in the same scene. The Network Density is a measures of how complete is the network (ie. all possible edges between its nodes). As you can see, Macbeth himself is at the centre of several poorly connected groups of people in the play.

The second example is from the Moovel Lab web page. You can check out the interactive graphic there. What the network shows is all of the roads that lead to Rome (ie. the shortest road route to Rome from any given point in Europe or Asia Minor). You will note that it is basically tree-like, as expected, but the sea routes form reticulations.

The third example is from Kieran Healy's blog. You can read the full explanation there. It concerns the historical figure Paul Revere, who was involved in the American Revolution. The fable tells us that he rode through the night calling out "The British are coming", but for a number of simple reasons this must be pure poppycock. The following network shows you what was his real role. There were a number of groups of people who banded together to ignite the revolution, and the members of these groups are connected pairwise in the network. The network is very clustered, indicating that these groups had few members in common. If you look closely, you will see that Paul Revere was the only person involved in all of the groups. This makes him a far more important person that history has credited him.

I think that interaction networks are fun, as well as informative.

Are taxonomies networks?

One of the basic tenets of modern systematics is that taxonomies should be hierarchical. That is, we arrange things in a nested hierarchy, with decreasing similarity among the objects as we proceed towards the tip. Indeed, one of Darwin's arguments for his version of biological evolution was that specie splitting leads naturally to a hierarchical taxonomy.

However, it is clear that not everyone agrees with this idea. The web is full of things labelled "taxonomy" but which are clearly networks. I have gathered a few of them here for you.

The first example is from Business Insider UK, Everything you need to know about beer, in one chart. It seems to be quite informative.

An even more complex version, and thus much more network-like, is available at Pop Chart Lab: The magnificent multitude of beer. However, this is not labelled as a "taxonomy". Just as an aside, there is also A periodic table beer styles (an earlier version is here).

The next one is ubiquitous on the web, but appears to come from Charley Chartwell: A grand taxonomy of Shakespearean insults. It may give you some good ideas!

The next one also comes from Pop Chart Lab: The grand taxonomy of rap names.

Here is a version without the centre obscured, although it is no longer labelled as a taxonomy:

Next we have one from Stephen Wildish: The fish & chip taxonomy.

This final network is a bit more cheeky than the others. It is also from Stephen Wildish: A taxonomy of arse.

There are many other "taxonomies" out there, many of which are basically star trees, with very few being truly tree-like. Here is a simple "tree" taxonomy, which comes from Kate Turner: The taxonomy of my music. Unfortunately, I think that in reality it should probably be a network, like the others.

Wigwag, and the Family Tree

I have noted before that common usage of expressions like "family tree" often extend far beyond actual pedigrees. This particular expression is often used to describe any sort of historical relationship, not just genealogical ones. It is also sometimes used simply to describe any sort of personal inter-connection. All of these usages occurred in a short-lived magazine from 25 years ago called Wigwag.

Wigwag magazine formally debuted in October 1989 (after a test issue in 1988), and published its last issue in February 1991, for a total of 15 issues. It was a sort of cozy version of the New Yorker magazine. Similarly, it had a number of regular features, such as the Road Trip, the Map, and Letters From Home. The one that is of interest to us was called The Family Tree.

This feature mapped cultural relationships, having been described as "a field guide to the genealogy of influence in American life". It included human relationships, but it also included things like cars (the tree of which is reproduced in the book by Nobuhiro Minaka & Kunihiko Sugiyama. 2012. Phylogeny Mandala: Chain, Tree, and Network) and comic-book superheroes.

I have been unable to locate any decent copies, but four of the "trees" are included below.

As you can see, sometimes The Family Tree was actually a genealogical tree, but just as often it was simply a network of pairwise cultural connections. The latter, of course, usually formed a complex network that did not really map historical relationships.

This last Family Tree is from the original trial issue, and shows the inter-relationships of the writers and producers of American TV sitcoms.

You can read a bit more about the magazine, and its history, here:

• Design Magazines
• The Awl
• Folio
• Chicago Tribune

Visual complexity and phylogenetic networks

Network diagrams have become rather commonplace in the modern world. Most of them are constructed along the same lines — observed entities (objects or concepts, or groups of them) are connected by lines showing observed relationships. Such visualizations are relatively easy to create using computers, and so they represent a relatively new form of visual data analysis. The complexity of the diagrams can be both seen and quantitatively analyzed, thus forming part of what is now grandiosely called "data mining and knowledge discovery".

The Visual Complexity project has been compiling an interesting set of online network visualizations. While the author (Manuel Lima) intends this to be "a unified resource space for anyone interested in the visualization of complex networks", at the moment it is simply a magpie collection of references to web pages. There are currently nearly 800 visualizations referenced, grouped into:

• Art
• Music
• Biology
• Food Webs
• Transportation Networks
• Business Networks
• Social Networks
• Political Networks
• Computer Systems
• Internet
• World Wide Web
• Pattern Recognition
• Semantic Networks
• Knowledge Networks
• Multi-Domain Representation
• Others

Our interest is in the Biology group, of course, where we have long known about networks, including food webs, which you will notice are grouped separately. There are currently 52 networks (plus 8 in the Food Web group), covering a wide range of topics, such as:

• Gene interaction networks
• Protein-protein interaction networks
• Protein "homology" networks
• Neuron networks
• Haplotype blocks
• Metabolic pathways
• Genome maps
• Physiology maps
• Disease maps
• Visualizing the aging process

This is all very well. However, we are specifically interested in phylogenetic networks, which are as old-fashioned as food webs. They differ significantly from these other biological networks. Phylogenies connect observed entities (objects, or groups of them) only indirectly, via unobserved nodes, with the lines representing inferred affinity or genealogical relationships. Only at the population level is it likely that all internal nodes, representing individuals, will be observed, and that their relationships might also be observed.

There are currently three phylogenies referenced by Visual Complexity:

• Tree of Life
• Mammal Supertree
• Microbial Evolution

Only the last of these is a network, the other two being trees. Sadly, the first one also contains a dead link, which is a problem common for most multi-year internet projects.

Unfortunately, the uniqueness of phylogenies among networks is not acknowledged by the Visual Complexity site. This is not unusual amongst network researchers, most of whom have never even heard of phylogenies. Moreover, many of the people who do seem to have heard of them often fail to understand them and their interpretation, so that they do not notice the fundamental difference. Nevertheless, phylogenetic networks are among the oldest type of recorded network, and there are certainly complex versions of them dating back to the 1700s (see those by Herman and by Batsch in Affinity networks updated).

Finally, the Visual Complexity site does not yet have much from anthropology (as distinct from the social sciences in general) or anything from linguistics (other than programming languages!). These are promising areas for studies of visual complexity.

Network of magicians

In 1965, Christopher Alexander published a classic paper called A City is Not a Tree, in which he pointed out to town planners that human beings naturally arrange themselves spatially in networks, not in the neatly ordered tree-like arrangements then in favour. So, road and rail systems, for example, should be inter-connected networks rather than bifurcating trees leading to / from a single root (e.g. a Central Station). The classic image of a rail system as a network is the one produced by Harry Beck in 1931-1933 that illustrates the London underground as a circuit diagram, which is now widely imitated.

Part of the 1933 map

This image has inspired other network makers, including Tom Crosbie, a professional magician from the UK. He has recently produced the following diagram, which illustrates some of the characteristics shared by a large number of the world's magicians. Note that much of the complexity comes from trying to illustrate each characteristic separately.

Some parts of the diagram do not make sense. Why, for example, are Apollo Robbins and Ava Do apparently at the same point? And also Mike Caveney and Tina Lenert? Why do only Penn & Teller have four intersecting lines, and no-one else?

It is, of course, easy to recognize the limitations of the sampling, since it is heavily biased towards English-language magicians. In particular, in spite of the existence of a "Competitions" category, even a cursory look at the Fédération Internationale des Sociétés Magiques (FISM) World Championships of Magic winners, shows that many recent Grand Prix recipients are missing, including Ivan Necheporenko (Russia), Vladimir Danilin (Russia), Franklin (Germany), Norbert Ferré (France), Jason Latimer (USA) and Rick Merrill (USA). From the German collective known as The Flicking Fingers, only Pit Hartling is included, but not Nicolai Friedrich, Manuel Muerte or Gaston, each of whom has two FISM titles, nor Thomas Fraps or Jörg Alexander, both of whom have one. The absent Arsene Lupin (Poland) has also been a consistent title winner (three times).

Recent UK magicians such as Young & Strange are included but Brynolf & Ljung (Sweden) are not. Very few Asian magicians are included, who have dominated much of the recent talk about magic; notably absent are Han Seol Hui and Kim Hyun Joon. Also, absent is Xavier Mortimer (France), the most prominent on the practitioners who see magic as a performance art (he combines mime, music and illusion). You can add your own list of favourite absentees.

This is not an example of a phylogenetic network, of course, since the people are directly connected rather than connected via inferred ancestors.

Network measures and phylogenetic networks

Recently, I considered the relationships between phylogenetic networks and other types of biological network. I concluded that they may be quite different. This further suggests, that much of the theoretical work being directed towards the study of those networks ("network science"; eg. Newman 2010) may not turn out to be particularly relevant for phylogenetic networks, at least from the biological perspective. However, that does not mean that we should not look further into the idea.

One major aprt of the study of other biological networks has been the development of descriptive summaries of the network charactertistics. These characteristics are usually summarized by one or more mathematical measurements. This does not necessarily mean that biologists have seen any close relationship between these mathematical measures and biologically relevant quantities, but they are working on it.

So, it is worth considering whether any of these network measures have yet played a role in phylogenetic networks.

Network Measures

Properties of individual nodes

Node degree — number of incident edges to a node

• for a dichotomous tree this is pre-defined (indegree 1, outdegree 2), and many network models have similar restrictions (eg. indegree 2, outdegree 1 for reticulation nodes)
• however, applying the coalescent to a population network suggests that the node with the largest degree is the most probable common ancestor, so it is potentially of interest here

Degree distribution — frequency distribution of the degree for all nodes

• not used so far, presumably because it would be uninteresting in light of the previous comment

Properties affected by local subgraphs of the network

Clustering coefficient — the degree to which nodes cluster together, measured as the density of triangles in the network (can also be a global measure)

• not used so far

Distribution of network motifs — motifs are connectivity-patterns that occur more often than expected, usually expressed as a frequency distribution

• not used so far

Properties affected by the whole network

Closeness — inverse of the summed shortest pathlengths to all other nodes, often averaged across all nodes

• not used so far

Betweenness — number of inter-node shortest paths on which a node lies, often averaged across all nodes

• not used so far

Node density — number of nodes per unit pathlength

• not used formally, as far as I know, but phylogeneticists have consistently (and perhaps inappropriately) distinguished highly branched (speciose) parts of a tree from unbranched parts

Centrality — can be measured with respect to degree, closeness or betweenness

• not used so far

Network diameter — either the average minimum distance between pairs of nodes, or the longest pathlength between any pair of nodes (relative to the number of nodes)

• has sometimes made its appearance as a statistic in the phylogenetic literature
• has been used as an optimality criterion for distance-based tree-building
• if nothing else, the maximum diameter is used for mid-point rooting of a tree

Nestedness — quantifies whether the structure of small assemblages is a proper subset of the structure of large assemblages

• a dichotomous tree is fully nested, and so nestedness has had a leading role in phylogenetics
• nestedness could be used to measure the tree-likeness of a network

Fractal structure — quantifies the similarity of network structure at different scales

• not used so far, although tree-imbalance (inversely related to fractal structure) has been an important measurement for trees

Network resolution — amount of information contained in the network (i.e. how much of the variation in node and edge behaviour is retained in the network representation) e.g. unrooted < rooted < rooted with variable edgelengths

• of interest but usually not quantified
• an unrooted tree/network cannot represent evolutionary history
• use of variable edgelengths is common for rooted trees but not so far for rooted networks
• variable edgelengths are used in unrooted networks

Conclusions

So, most of these measures have not yet played a significant part in the development of phylogenetics. Instead, phylogeneticists have concentrated on quantifying the fit of their data to the trees, such as the consistency index, retention index or permutation tests (for parsimony), likelihood scores (for ML) and posterior probabilities (for bayesian), or they have considered "support" for individual edges, via procedures such as the bootstrap, various parametric statistical measurements, and the posterior probability of clades.

This distinction between phylogenetics and biological networks seems, once again, to come from the different way that the networks are constructed. The other networks are usually constructed directly from observed objects and interactions, so that interest focuses on a description of the resulting network. Phylogenetic networks, on the other hand, are inferred via optimization of the data and a model, so that interest focuses on the quality of the inference rather than on a description of the network.

It seems likely, therefore, that this situation will continue, as most of these measures are specifically designed for describing empirically observed networks. However, the somewhat more nebulous concept of "network robustness" (the degree to which a network structure is affected by removal or alteration of nodes) has been seen as an important characteristic in the study of all biological networks.

As noted by Proulx et al. 2005: "The hope is that network approaches will ... reveal the global patterns behind large-scale ecological and evolutionary processes. The fear is that all of the fine structure will still matter in the end, leaving us tangled in detail."

References

Newman M.E.J. (2010) Networks: An Introduction. Oxford University Press, Oxford.

Proulx S.R., Promislow D.E.L., Phillips P.C. (2005) Network thinking in ecology and evolution. Trends in Ecology & Evolution 20: 345-353.

Biological versus phylogenetic networks

Networks have recently begun to receive serious attention in nearly all areas of biology. There has been a new focus on complex networks embedded within biological systems; and the mathematical properties of those networks are now being actively studied. In this sense, the interest in phylogenetic networks is simply part of a much larger movement.

An important point, however, is whether the characteristics of the different biological networks have anything in common. The nodes, for example, can represent units at all levels of the biological hierarchy, from elements, through organic and inorganic compounds, to tissues, organs, individuals, populations, species, communities and ecosystems. The edges (or arcs) represent all sorts of interactions between the nodes, including transcriptional control and other biochemical processes, energy and nutrient flow, behavioral interactions, and genetic or genealogical relationships.

Does this complexity mean that we have networks of fundamentally different type, or do the networks differ only in a few mathematical details? Importantly for our purposes, are phylogenetic networks essentially different from other biological networks? If so, then developments elsewhere do not necessarily flow on to us. Indeed, phylogenetic networks seem to be unknown to many network biologists. For example, phylogenetics is not even mentioned in this review paper, which implies some sort of disconnection: Proulx, Promislow, Phillips (2005) Network thinking in ecology and evolution. Trends in Ecology & Evolution 20: 345-353.

I will argue here that, indeed, phylogenetic networks do not match any other type of biological network.

Network Characteristics

First, we can list some of the important characteristics of phylogenetic networks if they are to represent evolutionary history, and then consider them individually:

1. fully connected
2. directed
3. single root
4. each edge (arc) has a single direction
5. no directed cycles
6. in species networks the internal nodes are usually unlabelled, although in population networks some / many of them may be labelled.

Most other biological networks can be disconnected, at least potentially, because the definition of the nodes to be included in the network is often independent of the network itself, so that there is no necessary connection between nodes. For example, the species within a local community may not all be connected to each other with respect to the characteristic being studied (eg. genetic relatedness). Indeed, finding this out may be a primary goal of any particular study. Similarly, molecular compounds usually form at least semi-independent sets of pathways, so that the study of any one organ can produce disconnected networks. With evolutionary history, on the other hand, all conceivable nodes are connected to each other by definition (unless there are multiple origins and subsequent history of life in the Universe).

Protein interaction network

In order to represent history, which has a single time direction, a phylogenetic network must have directed edges (arcs) to represent the time course. Many other biological networks have no explicit direction, even if there is an implied one. For example, in protein-protein interaction networks the edges represent the presence of physical interactions between proteins (with no implied direction), and in genetic-relationship networks the edges simply represent the degree of genetic relatedness of individuals (eg. the link between siblings has no explicit direction, although there is an implied directional link to their parents).

In a phylogeny there is usually a single root, because phylogeneticists try to work on monophyletic groups (clades); and if they really do want to study the Tree of Life then there is assumed to be a single origin of life in the Universe. Once again, for other networks the definition of the included nodes is often independent of the network or its shape, so that a single root is not necessary. For example, networks of regulatory interactions among genes are often represented with the nodes around the perimeter of a circle with the edges being chords. Furthermore, in food webs the arcs represents who eats whom, and these networks are called "webs" for a good reason: there is usually no obvious root position. Indeed, the usual representation of a food pyramid starts with multiple sources (at the bottom) and a single sink (at the top), with the arc directions indicating "is eaten by".

Gene regulatory network

Also, many biological networks have directed cycles. For example, the feedback loops in biochemical pathways are usually important (as sometimes are feedforward loops). Indeed, the discovery of feedback has been considered to be a major contribution to our understanding of why biological systems are different from non-biological ones. The recycling of nutrients in ecosystem nutrient pathways is another prominent example, although no feedback is involved in this case. Once again, the recognition that the Earth is effectively a closed system with finite resources that must be reused is considered to be a major contribution by biology.

Moving on, many networks have bidirectional arcs, indicating direct interactions between nodes. Indeed, many behavioral systems show this feature, including intra- and inter-competition networks in ecology as well as sexual-contact networks (which, incidentally, have two distinct types of nodes). Immunological networks often have this characteristic, as well, with the arcs pointing in one direction or the other at different time points during a cell's immunological reaction to a stimulus. (These networks also can have nodes with arcs that point directly back to themselves, indicating that a molecule regulates itself.) Host-parasite systems can also be considered to have bidirectional arcs, although in this case the paired arcs represent different processes (the effect of the parasite on the host and the host on the parasite operate via different mechanisms). In this case, two separate arcs are usually used, rather than a single bidirectional one, thus representing a directed cycle.

Predator-prey systems may, on occasion, match phylogenetic networks. If we isolate the predator-prey relationships from all of the others in a food web then a single tree-like structure sometimes emerges, with a single "key" predator at the root and a series of non-predators at the leaves. However, more often there are several "root" predators within any one community predator-prey network. Similarly, disease-transmission networks can be tree-like if there is a single identifiable origin to an epidemic, for example, but not otherwise. Note that the internal nodes are all labelled in both of these types of network, so that they will match a population network rather than a species network.

HIV partner network

Conclusion

Almost all types of biological networks are built by starting with a labelled set of nodes and then directly linking those nodes with edges — phylogenetic networks seem to be the only major class of biological networks in which some or many extra nodes are inferred by the network-building process. That is, almost all other networks are built empirically, by using a collection of observed nodes and connecting them via observed edges ("observed" indicating that there are experimental data). Phylogenetic networks, on the other hand, attempt to reconstruct unobserved (and unobservable) historical relationships using data, a model and a mathematical optimization procedure.

So, I have been unable to think of any other biological networks that do match all of the important characteristics of a species network. Perhaps some of you may be able to come up with a good example?

Update: This later post considers the summaries used for biological networks and whether they apply to phylogenetic networks.