Tuesday, April 08, 2008

Laplacian Kernel, Resistance Distance and Commute Time

The Laplacian kernel for a graph is interestingly connected to the resistance distance (the total resistance between two nodes) and the commute time (the average length of a random walk between two nodes) over the graph.

2 comments:

Anonymous said...

As you seem aware about this topic, I would have like to know if you knew about the way to compute the average number of time an edge is visited when randomly walking a graph from a vertex to an other vertex in terms of elements of the pseudo inverse of the laplacian matrix of the graph.

There are some results to compute commute time distance in terms of the pseudo inverse matrix so I guess there should be ways for my broblems.

Thank you !

Dell Zhang said...

Maybe what you need is the PageRank of the given graph's line graph?