Resistance and collaboration

I am certain that this is well known. But I was asked the question just before a not very inspiring lecture, and had nothing better to do than find my own proof.

Given any finite connected graph with positive numbers on the edges, we can regard it as an electrical network (the numbers are resistances). Now given two vertices v and w, connect the terminals of a V-volt battery to v and w and measure the current I; then the effective resistance between v and w, say R(v,w), is defined to be V/I.

Theorem R is a metric on the vertex set of the graph.

The proof depends on a lemma:

Lemma If we connect the terminals of a battery to two vertices v and w, then the potential of any other vertex lies between the potentials of v and w.

The highbrow proof of this is to observe that potential is a harmonic function, and takes its maximum and minimum values on the boundary, which in this case is the set {v,w}. (This hints that the theorem is true in much greater generality, of course.) But there is a down-to-earth proof using Ohm’s and Kirchhoff’s laws. Suppose, say, that there is a vertex with potential less than that of v and w. Let x be a vertex with minimum potential. Then every neighbour of x has higher potential, and so every edge through x carries current in to x. By Kirchhoff’s current law, all these currents must be zero, so all neighbours of x have the same potential. By induction and connectedness, all vertices have the same potential, a contradiction.

Now we can prove the theorem. It is clear that R(v,w) is non-negative, and zero only if v=w; also that it is symmetric in v and w. We have to prove the triangle inequality: R(u,v)+R(v,w) ≥ R(u,w).

Let r1 = R(u,v), and r2 = R(v,w). We define two current flows in the graph as follows. For the first one, we connect a battery with voltage r1 to u and v. This causes unit current to flow out of u and into v. If P1 denotes the corresponding potential, then P1(u)−P1(v) = r1, and P1(v)−P(w) ≥ 0, by the lemma.

Similarly, a battery of voltage r2 connected to v and w causes a unit current to flow out of v and into w; the potential satisfies P2(v)−P2(w) = r2, and P2(u)−P2(v) ≥ 0.

Since Ohm’s and Kirchhoff’s Laws are linear, we can add these two solutions. The resulting solution has a unit current flowing out of u and into w. With P=P1+P2, we thus have P(u,w) = R(u,w), and so

R(u,w) = P(u,v)+P(v,w) ≤ r1+r2.

So the proof is done.

I am writing this at the LMS-EPSRC Durham Symposium on Graph Theory and Interactions. There has been some talk about “intrinsic metrics” for graphs; I am not sure I have completely grasped these yet, and in any case they con’t seem to be unique. But I think resistance distance has quite a lot to recommend it.

For one example, it occurs in experimental design. In a comparative experiment based on a block design, the variances of estimates of treatment differences are proportional to the effective resistances between corresponding vertices of the concurrence graph. Minimising the average of these resistances gives a so-called A-optimal design.

Another relevant area might be the collaboration graph. If you go to MathSciNet, you can find the distance between two mathematicians in this graph (in which two people are joined by an edge if they are joint authors of a paper). Variants of this have been proposed, taking account of multiple joint papers; but it seems to me that the resistance distance is a very natural way to do this. Not only will researchers with many joint papers be closer, but researchers with many co-authors will also be closer.

Could we expect one day to see a computation of resistance distance available on MathSciNet? It is not so hard to compute. They have the data on the graph already. According to the Erdős Number Project homepage, of the 400000 mathematicians who have published papers, about 80000 have no co-authors at all (and so are isolated vertices), 50000 lie in small components with size from 2 to about 50, and the remaining 270000 lie in a “giant component”. Moreover, the average number of coauthors is 3.36, so this graph is quite sparse.

To compute effective resistance between v and w, we take the Laplacian matrix of the graph (with minus the weight of the edge {v,w} in the (v,w) position, and the diagonal entry adjusted so that the row sums are equal to 0); find its Moore-Penrose generalized inverse; look at the 2×2 submatrix corresponding to the rows and columns indexed by v and w; and then add the diagonal entries and subtract the off-diagonal entries. For a sparse graph, finding the Moore-Penrose inverse is not too difficult; and this only needs to be done once (until the graph changes and the calculation must be updated). For the calculation, pendant vertices can be ignored and added back in afterwards. (There may be quite a few of these, for example students who have written papers only with their supervisors.)

Some decisions will have to be made about multiple joint papers and multiple-author papers. Perhaps it is better to think in terms of conductance (the inverse of resistance). If every joint paper of two authors counts, we simply add the conductances (this is equivalent to having multiple edges in the graph). For an n-author paper, we may want it to contribute less than 1 to the conductance between any two authors, since it also adds many alternative routes between them. In a complete graph on n vertices, the effective resistance between any two vertices is 2/n, so scaling conductances by this factor may be appropriate.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, exposition and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s