Paper Info
Title
Incremental Commute Time Using Random Walks and Online Anomaly Detection.
Abstract
Commute time is a random walk based metric on graphs and has found widespread successful applications in many application domains. However, the computation of the commute time is expensive, involving the eigen decomposition of the graph Laplacian matrix. There has been effort to approximate the commute time in offline mode. Our interest is inspired by the use of commute time in online mode. We propose an accurate and efficient approximation for computing the commute time in an incremental fashion in order to facilitate real-time applications. An online anomaly detection technique is designed where the commute time of each new arriving data point to any data point in the current graph can be estimated in constant time ensuring a real-time response. The proposed approach shows its high accuracy and efficiency in many synthetic and real datasets and takes only 8 milliseconds on average to detect anomalies online on the DBLP graph which has more than 600,000 nodes and 2 millions edges.
Year
DOI
Venue
2016
10.1007/978-3-319-46128-1_4
ECML/PKDD
Field
DocType
Citations 
Anomaly detection,Laplacian matrix,Graph,Random walk,Matrix (mathematics),Computer science,Algorithm,Commute time,Artificial intelligence,Eigendecomposition of a matrix,Machine learning,Computation
Conference
2
PageRank 
References 
Authors
0.37
14
2
Name
Order
Citations
PageRank
Nguyen Lu Dang Khoa1628.44
Sanjay Chawla21372105.09