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/

This entry was posted in Uncategorized. 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