  Commute Time Distance (CTD) is a random walk based metric on graphs. CTD has
found widespread applications in many domains including personalized search,
collaborative filtering and making search engines robust against manipulation.
Our interest is inspired by the use of CTD as a metric for anomaly detection.
It has been shown that CTD can be used to simultaneously identify both global
and local anomalies. Here we propose an accurate and efficient approximation
for computing the CTD in an incremental fashion in order to facilitate
real-time applications. An online anomaly detection algorithm is designed where
the CTD of each new arriving data point to any point in the current graph can
be estimated in constant time ensuring a real-time response. Moreover, the
proposed approach can also be applied in many other applications that utilize
commute time distance.
