PageRank and resistance
In class, we have discussed the PageRank algorithm for assigning importance values to nodes in a graph through the hub-and-authority model. However, it is also possible to formulate the algorithm in terms of a random walk as follows: for a given vertex, the random walker will move to a neighboring vertex with probability alpha, or move to a non-neighboring vertex with probability 1-alpha. This is analogous to a user at a current webpage either going to a linked webpage or going to another, unlinked webpage. There also exists a more generalized version of the algorithm which accepts a probability distribution of the starting nodes (in the standard algorithm, this distribution is just the uniform distribution), which will be used in the discussion going forward.
From this random-walk formulation of PageRank that starts at a certain probability distribution of nodes, we can construct a way to compute the “resistance” between two nodes u and v. To get a better sense of this, imagine that an electrical current was placed in the graph through node u and v and we were to compute the resistance of said current between those two points. This notion of resistance can be computed through various aspects of the graph itself (for example, its normalized signed degree matrix, its Green’s function, and its Laplacian; further details can be found in the paper cited), and from this, we can also obtain a notion of voltage of the graph, through a generalized notion of Ohm’s law.
Next, we define the hitting time between two nodes u, v to be the expected number of iterations for a random walk starting at node u to reach node v, and the commute time between u and v as the sum of hitting times between u and v and v and u. The paper then shows an interesting result; the commute time between nodes u and v is equal to the resistance between u and v divided by the voltage of G. Likewise, the paper then goes to show how PageRank can be defined as a generalized version of hitting time, and thus shows that the resistance between two nodes can be computed as a linear combination of PageRank values between the nodes. I find it intriguing that two seemingly unrelated concepts (resistance in physics and PageRank in information theory) can have such a connection.
Source: https://www.math.ucsd.edu/~fan/wp/lov.pdf