Graph symmetries

Author: Christoph Hauert

Circulations represent a vast class of population structures characterized by the feature that for each vertex the sum of the weights of incoming links equals the sum of the weights of outgoing links. Intuitively this balance means that each individuals' impact on its neighbourhood is the same as the impact of its neighbourhood on the individual. According to the circulation theorem mutants on all graphs that are circulations result in the same fixation probability for the spatial Moran process. In fact, the fixation probability is even the same regardless of the location where the initial mutant arises. Thus, circulations capture an essential symmetry requirement for graphs with respect to fixation probabilities. Due to the generality of circulations, fixation probabilities are a highly robust quantity and naturally an important determinant of evolutionary processes.

An equally important determinant of evolution are fixation times but those turn out to be much more fickle because they are highly sensitive to the structural details of the underlying graph. More specifically, even among circulations the fixation times can differ widely, depending on how easily a mutant can spread. For example, a ring graph (or cycle) results in much longer fixation times than a complete graph because the ring structure severely limits opportunities for mutants to occupy additional vertices. Nevertheless, the corresponding fixation probability remains unchanged. This illustrates that it seems unlikely that some equally powerful criteria exist that characterize graphs with identical fixation times. At the very least such symmetry criteria would be much more limited than the equivalent requirement of circulation graphs to preserve fixation probabilities.

A significantly weaker symmetry requirement is to identify graphs for which the fixation times do not depend on the location of the initial mutant (McAvoy & Hauert, 2015). For example this applies to the aforementioned ring graph or complete graph: even though the fixation times are hugely different on the two graphs, the initial placement of the mutant on either graph has no effect on its fixation time. In contrast, this does not apply to e.g. random regular graphs in general. Also note that the meaning of the term 'fixation time' is somewhat ambiguous because it could either refer to the time it takes for a mutant to take over the entire population, or to the time that the population returns to either absorbing state of all residents or all mutants. To be more precise, the former is referred to as the 'conditional fixation time', i.e. conditioned on the mutant's fixation, while the latter is the 'unconditional fixation time', or, equivalently, the 'absorption time'.

Fixation times on circulations

The following sample graphs illustrate the susceptibility of fixation times to the initial location of the mutant. All graphs shown are regular (every vertex has the same number of neighbours) and undirected (all links are undirected, i.e. bi-directional). All regular graphs are circulations and hence result in identical fixation probabilities but conditional fixation times as well as absorption times vary between graphs. However, whether fixation times also vary based on the initial location of the mutant depends on additional structural symmetries. For the examples below the degree of structural symmetry (beyond regularity) increases from top to bottom.

Fixation times on the Frucht graph

The Frucht graph is a cubic graph without any automorphisms apart from the identity map, which means it is a graph with degree three (every vertex has three neighbours) and no additional structural symmetries. In fact, it is the smallest such graph with only twelve vertices. Due to the lack of symmetries, the fixation and absorption time is different for every node.

Fixation times on the Tietze graph

Tietze's graph is another cubic graph again with twelve vertices but with a higher degree of symmetry. More specifically, it has twelve automorphisms but is not vertex-transitive. The increased structural symmetry manifests itself in fixation and absorption times that are equal for some nodes but differ for others.

Fixation times on the Franklin graph

The Franklin graph is again a cubic graph with twelve vertices but this graph is now also vertex-transitive. However, as it turns out vertex-transitivity is insufficient to ensure fixation/absorption times that are independent of the mutant's initial location. As on Tietze's graph some vertices have identical fixation probabilities but not all.

Fixation times on the Heawood graph

Unfortunately no cubic graphs with twelve vertices exist that satisfy the still stronger structural symmetry requirements of arc-transitivity also simply called symmetric graphs. Alternatively, the Heawood graph is a slightly bigger cubic graph with fourteen vertices. For symmetric graphs the fixation and absorption times are independent of the placement of the initial mutant but even on symmetric graphs fixation times differ between graphs.

Fixation times on the Icosahedron graph

Another example of a symmetric graph is the icosahedron graph, which has twelve vertices but is of degree five, i.e. every vertex has five connections. Again the fixation and absorption times are the same for every vertex but are different from the Heawood graph.

Publications

1. McAvoy, A. & Hauert, C. (2015) Structural Symmetry in Evolutionary Games J. R. Soc. Interface 12 20150420 doi: 10.1098/rsif.2015.0420