Fast matrix computations for pair-wise and column-wise commute times and Katz scores

Details Fast matrix computations for pair-wise and column-wise commute times and Katz scores Fast matrix computations for pair-wise and column-wise commute times and Katz scores

2011-04-19

arxiv.org/abs/1104.3791v1

Computer Science

Social and Information Networks

35 pages, journal version of http://dx.doi.org/10.1007/978-3-642-18009-5_13 which has been submitted for publication. Please

Scientific paper

10.1080/15427951.2012.625256

We first explore methods for approximating the commute time and Katz score between a pair of nodes. These methods are based on the approach of matrices, moments, and quadrature developed in the numerical linear algebra community. They rely on the Lanczos process and provide upper and lower bounds on an estimate of the pair-wise scores. We also explore methods to approximate the commute times and Katz scores from a node to all other nodes in the graph. Here, our approach for the commute times is based on a variation of the conjugate gradient algorithm, and it provides an estimate of all the diagonals of the inverse of a matrix. Our technique for the Katz scores is based on exploiting an empirical localization property of the Katz matrix. We adopt algorithms used for personalized PageRank computing to these Katz scores and theoretically show that this approach is convergent. We evaluate these methods on 17 real world graphs ranging in size from 1000 to 1,000,000 nodes. Our results show that our pair-wise commute time method and column-wise Katz algorithm both have attractive theoretical properties and empirical performance.

Affiliated with

Also associated with

No associations

Rating

Fast matrix computations for pair-wise and column-wise commute times and Katz scores does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast matrix computations for pair-wise and column-wise commute times and Katz scores, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast matrix computations for pair-wise and column-wise commute times and Katz scores will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-183489