## My Paper on Fast matrix computations for commute times and Katz scores

I posted a journal version of the “Fast Katz and commute time” paper from WAW2010 to arXiv entitled “Fast matrix computations for pair-wise and column-wise commute times and Katz scores”

Commute time scores and Katz scores are useful ranking, link predictions, and clustering metrics.  Given a graph, they are defined between any pair of nodes.  Computing all of the scores at once takes $O(n^3)$ work and $O(n^2)$ memory ($n$ is the number of nodes).  What we investigate are faster algorithms that compute a single score in $O(n)$ memory and time; and column-wise algorithms that approximate the score between a single node and all other nodes (think Dijkstra’s algorithm here) with similar computational efficiency.

The major difference from the conference version is a much more thorough description of the pairwise algorithms, more extensive experiments, a fully explained convergence theory, and a column-wise algorithm for commute time.  Although, the latter algorithm is not that great.  However, that problem is not likely to be important as column-wise commute time distances are well approximated by the following constant time algorithm: $C_{i,j} \approx 1/d_i + 1/d_j$ where $d_i$ is the degree of node $i$.  This formula was derived by von Luxburg et al.  A recent paper they wrote explains the issue clearly:

```Ulrike von Luxburg, Agnes Radl, and Matthias Hein.
Getting lost in space: Large sample analysis of the commute distance.
In Advances in Neural Information Processing Systems 24 (NIPS2010), 2010.
URL http://books.nips.cc/papers/files/nips23/NIPS2010_0929.pdf.```

We test this approximation with graphs up to 100,000 nodes and show that it’s really good.

As with most of my papers, the code for the project is online:

http://www.cs.purdue.edu/homes/dgleich/publications/2011/codes/fast-katz/