DenseAlert: Incremental Dense-Subtensor Detection in Tensor Streams
Kijung Shin (Carnegie Mellon University);Bryan Hooi (Carnegie Mellon University);Jisu Kim (Carnegie Mellon University);Christos Faloutsos (Carnegie Mellon University)
Abstract
Consider a stream of retweet events - how can we spot fraudulent lock-step behavior in such multi-aspect data (i.e., tensors) evolving over time? Can we detect it in real time, with an accuracy guarantee? Past studies have shown that dense subtensors tend to indicate anomalous or even fraudulent behavior in many tensor data including social media, Wikipedia, and TCP dumps. Thus, several approaches have been proposed for detecting dense subtensors rapidly and accurately. However, all these methods assume static tensors, while tensors evolve over time in many real-world applications such as social media and web. We propose DenseStream, an incremental algorithm that maintains and updates dense subtensors in a tensor stream (i.e., sequences of changes in a tensor), and DenseAlert, an incremental algorithm spotting the sudden appearances of dense subtensors. Our methods are: (1) Fast and
