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.

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:

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

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

You are commenting using your 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