## Abstract

When investigating evolution in structured populations, it is often convenient to consider the population as an evolutionary graph—individuals as nodes, and whom they may act with as edges. There has, in recent years, been a surge of interest in evolutionary graphs, especially in the study of the evolution of social behaviours. An inclusive fitness framework is best suited for this type of study. A central requirement for an inclusive fitness analysis is an expression for the genetic similarity between individuals residing on the graph. This has been a major hindrance for work in this area as highly technical mathematics are often required. Here, I derive a result that links genetic relatedness between haploid individuals on an evolutionary graph to the resistance between vertices on a corresponding electrical network. An example that demonstrates the potential computational advantage of this result over contemporary approaches is provided. This result offers more, however, to the study of population genetics than strictly computationally efficient methods. By establishing a link between gene transfer and electric circuit theory, conceptualizations of the latter can enhance understanding of the former.

## 1. Introduction

Recently, graphs have been employed in evolutionary biology as a convenient way of describing social structure [1–3]. In this set-up, the vertices are thought of as sites occupied by individuals and the edges as specifying which individuals interact with and to where they disperse their offspring. Specifically, I consider an undirected graph *G* with *N* vertices representing haploid individuals. I assume that the graph is transitive, meaning, for any vertices *a*,*b* ∈ *V*(*G*), there is an automorphism *f* of the graph such that *f*(*a*) = *b*. Intuitively, transitivity means that every site ‘looks’ the same; each site has the same number of neighbours and the same dispersal pattern to those neighbours. This is a common symmetry assumption found in the literature [4]; see Taylor *et al.* [3] for examples of transitive graphs. A consequence of the transitivity assumption is that all vertices have the same degree *k*.

Individuals disperse their offspring to neighbouring sites along edges of the graph. To simplify the exposition, I assume that dispersal is uniform; that the probability of dispersing an offspring to an adjacent vertex is 1/*k*. Here, I am concerned only with haploid individuals and focus attention on one genetic locus with two possible alleles, *A* and *B*. During reproduction either gene mutates at some small rate *μ* into the other. The *A* and *B* code for types of individuals, *A* for cooperator and *B* for defector, for example. Individual type is irrelevant, as are the population dynamics, for the present discussion, however, considering relatedness—a measure of the genetic similarity between individuals—is calculated in a neutral population, where neither *A* nor *B* confers a selective advantage on any individual. To facilitate understanding, the population can be thought of as undergoing a neutral Moran process [5]: an individual is chosen to die at random and is replaced by the offspring of one of its neighbours, chosen at random. The offspring is of the same genotype as its parent with probability 1 − *μ*.

Owing to the limited dispersal naturally present, evolutionary graphs are ideal systems to study the emergence of social behaviours, which are often studied within an inclusive fitness framework [6]. The difficulty in this is that the relatedness between individuals—an integral component of an inclusive fitness analysis—is often computationally infeasible. Typically, a system of linear recursions, specifying the probabilistic genealogy of the individuals, is constructed. These equations are then solved, yielding the probabilities of identity by descent (IBD), *r*_{ij}. The relatedness between individuals at *i* and *j* is then calculated as
where
is the average IBD between individuals in the graph, including between an individual and itself. The mutation rate *μ* is assumed to be small so that high-order effects are negligible. With this in mind, re-write the IBD expression with a Maclauren series, discarding all *μ* terms higher than first order:

This yields, 1.1This form of relatedness is the most convenient for the results that follow.

Graphs have a long history of being employed as abstractions of electrical networks: edges thought of as electrical components and vertices as the connections between them [7]. Here, I consider a graph as an electrical network with edges representing resistors each with resistance of 1*Ω*. To calculate the resistance between vertices *i* and *j*, a current *I*_{ij} from an idealized current source is applied to node *i* and drawn from *j*. This creates a voltage *V*_{ij} between *i* and *j*. The resistance *γ*_{ij} is then obtained via Ohm's law,

The average resistance is the sum of the resistances between all pairs of vertices,

This average includes the resistance between a vertex and itself, which, although equal to 0, yields a more compact equation.

Resistance is a way of measuring distance on a graph: the higher the resistance, the ‘further’ away two vertices are. In a sense, it is a more robust distance measure than the shortest-path measure as it accounts for all possible ways to reach a vertex. This property of resistance has led to an area of study aptly named *resistance distance* [8].

This is not the first work to introduce the resistance distance of a graph to biologically inspired problems. McRae & co-workers [9,10] have employed electric circuit theory to investigate landscape genetics. The current result extends previous work by applying electrical resistance to the calculation of genetic similarity between individuals on an evolutionary graph.

## 2. Results

The following result relates the resistance and relatedness concepts.

**Theroem 2.1.** *Let R*_{ij} *be the relatedness and γ*

_{ij}

*the resistance both between individuals i and j on a transitive graph G with N vertices each of degree k*.

*Then*,

This result may be proved through existing interpretations of resistance, which will be performed here. I phrase the result in terms of unweighted graphs, where the probability of dispersing along any edge is constant, 1/*k*, where *k* is the degree of any vertex. Although this simplifies the exposition, the result also holds for evolutionary graphs with unequal dispersal probabilities, provided that the transitivity of the graph is maintained. This follows from an observation that resistance may be calculated using results from the theory of random walks, which, in turn, do not require assumptions on the distribution of the transition probabilities. For a discussion of results in this vein, consult Chandra *et al.* [11]. Transitivity is, however, necessary and I highlight at which step of the proof of this result transitivity plays a role. I provide an example of an evolutionary graph with non-uniform dispersal probabilities at the conclusion of this section.

Electrical resistance in a circuit has long been known to correspond to random walks on the corresponding graph [12]. Recall that a random walk can be thought of as a particle starting at some vertex and moving to an adjacent vertex according to some probability distribution. For our purposes, the probability distribution will be uniform, 1/*k*. As stated previously, this is not a necessary assumption. Define *H*_{ij} to be the *hitting time*—the expected number of steps in a random walk that starts at node *i* and ends upon reaching node *j* for the first time. It is permissible for the walk to double back on itself, or to revisit the vertex *i*, as long as it terminates upon reaching *j*. As any random walk from *i* to *j* must start by transitioning to a neighbour of *i*, *H*_{ij} satisfies
for all *i* ≠ *j*, where the sum is taken over all vertices *m* adjacent to *i*. The hitting time can be related to the voltage *V*_{ij} between *i* and *j* according to Chandra *et al.* [11]. Here, for completeness, I paraphrase the arguments discussed by Chandra *et al.* [11].

Using an idealized current source, inject *k* amperes of current into all vertices and remove 2|*E*| amperes from *j*, where |*E*| is the number of edges of *G*. This creates voltages *V*′_{ab} in our circuit. Kirchhoff's current law states that the sum of the currents entering a node equals the sum of the currents exiting. This provides

From Ohm's law, and the unit resistances of the edges, we have,
for any adjacent vertices *a* and *b*. A property of voltage,
for any vertex *h*, combined with the previous two equations yields
or,
for all vertices *i*. Note that *H*_{ii} = *V*_{ii} = 0. From this, it follows that the hitting times and the voltages are equal up to a non-zero scaling factor. As *V*_{ab} = *V*_{ba}, it is seen that the *V*′_{ab} can also result from a circuit, where *k* amperes are removed from each vertex and 2|*E*| are injected in *i*. Both these circuits can be superimposed to yield an expression for 2*H*_{ij}. In so doing, the currents at each of the vertices cancel except for the 2|*E*| amperes injected in *i* and removed from *j*. Ohm's law provides,

Now, I return to relatedness; specifically, the form in equation (1.1). It has been shown [13] that *g*_{ij} satisfies
for all *i* ≠ *j*. The transitivity of the graph provides,
which yields,

This is the same condition for the *H*_{ij}. Observe that *γ*_{ii} = 0, whereas *R*_{ii} = 1, which provides that *H*_{ij} and *g*_{ij} are equal up to a non-zero scaling factor. From this, the result is established.

This equivalence between hitting times and identity by descent makes sense: the IBD expression is essentially tracking a random walk made by genes through evolutionary time. This interpretation will be revisited in §3.

### 2.1. Example 1

To illustrate the ease of calculations with the resistance distance compared with those involving the IBD, consider the cycle on *N* vertices (figure 1). This is a common example to consider [14,15]. Grafen [15] has derived the general expression for the relatedness between two individuals, which I recount here for dramatic juxtaposition. He does this through computing the IBD *r*_{n} between individuals *n* vertices apart by first establishing a system of recursions,
and then solving this recursion using matrix inversion. The solution is found to be

To calculate the relatedness observe that the limit of both the numerator and the denominator is 0. At this point, define the quantities and

Apply L'Hospital's rule twice and simplify to yield

The second-to-last equality is obtained by observing lim_{μ→0} *Q*_{n} = lim_{μ→0} *C* = 2.

Now I calculate the relatedness via the resistance. To do this I use two classic results in electronic circuit theory—Kirchoff's and Ohm's laws. Combining these two laws enables one to calculate the resistance in a parallel circuit: the reciprocal of the total resistance *ℛ* in a parallel circuit is the sum of the reciprocals of the resistances along each parallel component,

Assume the cycle as vertices connected by resistors of unit resistance. To find the resistance between two vertices *n* vertices apart, notice that there are two parallel circuits: one of length *n* and the other of length *N* − *n*. The resistance along the first is *n*, and *N* − *n* along the second. Hence, the total resistance is

The average resistance is

Therefore,

### 2.2. Example 2

Now I turn attention to a less trivial calculation. My intention here is twofold: to demonstrate the calculation of relatedness via the matrix methods developed in appendix, and to provide an example of a non-uniform dispersal pattern that satisfies transitivity. In this example, the population is structured on a toroidal lattice. A representation of this structure is provided in figure 2*a*—the edges of the bounding box indicate that the dashed (respectively, dotted) edges are identified. In this way, it is seen that vertex 1 is incident to vertices 2, 3, 6 and 7, and so on. The probability of dispersal in the ‘up’ and ‘down’ directions is both equal to 1/5, while dispersal in the ‘left’ and ‘right’ directions is both equal to 3/10. This is represented by the edge weightings in figure 2*b*. These weightings are the resistances of the edges, measured in ohms. The probability of dispersing in any one direction is the edge weighting in that direction divided by the sum of the weightings of all edges incident to the vertex dispersed from. Although this dispersal arrangement may seem cumbersome at first glance, it corresponds nicely to the previous set-up. Indeed, if the edge resistances are all set to 1, then the probability of dispersing along any edge is 1/4, where 4 is the (weighted, with weights 1) degree of the vertex.

The resistance between any two vertices may be calculated in a variety of ways, perhaps the easiest of which is using the matrix methods introduced in appendix. For a method to compute the resistance between vertices on a lattice of arbitrary size, see Wu [16].

With the vertex numbering in figure 2*a*, the Laplacian *L* is a 9 × 9 matrix with entries *L*_{xy} describing the incidence between vertex *x* and vertex *y*: if *x* = *y*, then *L*_{xy} is the negative (weighted) degree of the vertex, *L*_{xy} =−10; *L*_{xy} = 3/10 if *x* and *y* are horizontally adjacent; *L*_{xy} = 1/5 if they are vertically adjacent; and *L*_{xy} = 0 if *x* and *y* are not adjacent.

The pseudoinverse *Γ* for this example, found using computer algebra software, has entries *Γ*_{xy} according to the corresponding entries of *L*,

That is, if the *x* − *y* entry of *L* is −10, then the *x* − *y* entry of *Γ* is 5003/49 896, and so on. The resistance between vertices *i* and *j* is then found from entries of the matrix *Γ*, according to Klein & Randić [8]:
Averaging over all pairs of vertices yields,

The main result may now be employed to calculate the relatedness between individuals on the graph. For example, for individuals *x* and *y* that are horizontally adjacent,
for *x* and *y* vertically adjacent,
and for all other *x* − *y* pairs with *x* ≠ *y*,

## 3. Discussion

Although the example given here illustrates the possible computational advantage this method has over contemporary approaches, the true strength of this result is in the connections made between population genetics and electrical circuit theory. Both fields have developed independently for over a century. The present result indicates that there is a correspondence between, at least some of, the methods developed in either field. Indeed, the literature on resistance in electrical circuits contains many existing results that may shed light on genetic transfer in evolutionary graphs. Here, I discuss a few such results.

The theorem was proved via an interpretation of resistance *R*_{ij} as the expected number of steps in a random walk starting at vertex *i* and ending upon reaching vertex *j* for the first time, up to a constant. In terms of the probability of identity by descent, this analogy is still valid, but care needs to be taken in its interpretation. The random walk from *i* to *j* is thought of as not only traversing the graph *G* but also doing so back and forward through evolutionary time. As such, it is seen that the individual at vertex *i* is not necessarily the ancestor common to both *i* and *j*, rather, the common ancestor is some individual along the path of the random walk. This perspective is similar to that of coalescent theory [17,18], where the genes present in the individual at vertex *i* and those in vertex *j* are traced back in evolutionary time to a common ancestor.

The random-walk analogy has been employed in other applications of circuit theory to biologically inspired problems. McRae & co-workers [9,10] used electrical circuit theory to measure habitat fragmentation. There the random walk result is much more apparent: animals disperse their offspring through their environment. If a landscape feature creates an impediment to dispersal, then it is expected that the genetic differentiation between the populations which live on either side of this feature to be greater than in either population alone. Essentially, the more paths between populations, the lower the expected genetic differentiation between these populations. This is, in other words, the monotonicity principle for circuits: introducing resistors (paths) in an electric circuit either decreases the resistance between any two vertices, or leaves it unchanged. The key here is that resistance in electrical circuits measures more than strictly the shortest distance between vertices, it is a measure of the way vertices are connected; all ways of reaching one vertex from another are accounted for in the resistance, not just the shortest path. This property of resistance has been employed, using the analogous term *forest accessibility* [19], which is precisely the resistance [20], as a measure of relations in social networks [21].

For a final interpretation of resistance, it has been shown that resistance is related to the number of spanning forests of the underlying graph [22]. A tree of a graph *G* is a connected subgraph of *G* containing no cycles. A spanning forest of *G* is a collection of trees of *G* such that each vertex of *G* belongs to one tree. Denote the number of spanning trees of a graph *G* by *τ* and the number of spanning forests of *G* such that vertices *i* and *j* reside on the same tree by *τ*_{ij}. It can be shown, via the results of Chaiken [23] and Bapat [24], that

This offers another interpretation of relatedness. Writing the expression for relatedness as
3.1where *τ*_{ave} is the average *τ*_{kl} over all vertices *k* and *l*, the relatedness is revealed to be a normalized count of the number of trees of *G*. Trees of *G* can be thought of as genetic lineages. By specifying that vertices *i* and *j* must reside on the same tree, we ensure that they have a common ancestor. Essentially, the form of equation (3.1) communicates the idea that relatedness is the expected number of common ancestors for *i* and *j* relative to the average.

Extensions of the result presented here are quite possible and may correspond to developments in evolutionary graph theory. Indeed, despite the recent surge of interest in evolutionary graph theory, the field remains in its infancy. It is not entirely clear how to cast problems concerning haploid populations with more than two alleles, or those concerning populations of other ploidy, in an evolutionary graph–theoretic framework. Some work has been performed in this vein [25], but much more is needed. Another interesting extension of the current result would be in doing away with the transitivity assumption. As it stands, this assumption is quite necessary for the result to hold; the reader is invited to attempt to apply the result to graphs that violate, even slightly, the transitivity assumption.

## Acknowledgements

Thanks are owing to the Queen's University Mathematical Biology group who listened to my off-the-wall ideas, and specifically to Peter Taylor who patiently read and supplied invaluable comments on earlier versions of this manuscript.

## Appendix A

My intention here is to situate the main result of this article in the greater literature on resistance. Primarily, I will focus on the notion of resistance distance [8]. This appendix is intended to introduce to the reader a way of computing resistance using the Laplacian matrix of a graph. The Laplacian *L* of a graph *G* is the difference of the degree matrix *D* and the adjacency matrix *A*,
where *D* is a diagonal matrix with non-zero entry *D*_{ii} equal to the number of edges adjacent to vertex *i*, and *A* is such that *A*_{ij} = 1 precisely when vertices *i* and *j* are adjacent. As an example, the graph in figure 3 has Laplacian

A pseudoinverse *Γ* for a matrix *M* is a matrix of appropriate dimensions such that

Although not all matrices are invertible, all have a pseudoinverse. The pseudoinverse defined here is the Moore–Penrose pseudoinverse and can be shown to be unique. If *Γ* is the pseudoinverse of *L*, the resistance distance between vertices *i* and *j* is defined as [8],
A 1where the *Γ*_{ab} is the *a*,*b* entry of *Γ*. More conveniently, the resistance distance may be calculated with a theorem of Bapat *et al.* [26]:
A 2where ‘det’ is the determinant and *L*(*i*,*j*) is the matrix obtained from *L* by removing both the *i*th and *j*th rows and columns, and *L*(*i*) = *L*(*i*,*i*). These results offer a convenient method to compute the relatedness in an evolutionary graph. The Laplacian matrix is simple to write down by looking at the graph. Any major mathematics software can compute a pseudoinverse of a Laplacian matrix and the remaining work is straight arithmetic. As an example, consider the five-cycle in figure 1. The Laplacian for this graph, assuming a cyclical numbering of the vertices, is

The pseudoinverse is

Using equation (A 2), the resistance between vertices 1 and 3, say, is

The average resistance is easily found to be 4/5, which yields, via the theorem,

All other relatedness terms are found in a similar fashion.

- Received July 2, 2011.
- Accepted July 26, 2011.

- This journal is © 2011 The Royal Society