Dynamic PageRank with Decay: A Modified Approach for Node Anomaly Detection in Evolving Graph Streams

Abstract

Given a large graph stream with dynamically changing structures over a given timestep, it is important to detect the sudden appearance of anomalous patterns, such as sudden spikes in IP-network attacks or unexpected surges in social media followers. In addition, it is important that we promptly identify these abrupt changes in the network by considering swift and short-term responses within the network structure. To design a model capable of adapting to dynamic changes, we introduce an approach that utilizes a modified dynamic "PageRank-with-Decay" as a node scoring function. This method enables the detection of sudden dynamic graph changes based on node importance scores, leveraging the temporal evolution of graph structures at each timestep. This approach provides a refined anomaly detection mechanism for tracking rapid structural changes in the network. Through experiments conducted on a real-world dataset, our model demonstrates faster and more accurate results (in terms of precision and recall) compared to state-of-the-art methods.