Abnormal Evolution Pattern Recognition of Spatial Communities based on Random Walk with Restart

Identifying abnormal evolution patterns of spatial communities using vehicle trajectories provides valuable insights into urban traffic irregularities. Existing methods have primarily detected anomalies by tracking changes in the size of spatial communities. However, their effectiveness is limited by the inherent instability of spatial community detection methods. Additionally, these methods often fail to detect abnormal evolution patterns related to variations in internal connectivity and interaction intensity within communities. To address these limitations, we developed an Abnormal Evolution Pattern recognition method based on the Random Walk with Restart mechanism, referred to as AEP-RWR. First, a consensus clustering strategy was employed to derive stable community structures for each temporal snapshot, thereby mitigating the inherent instability in community detection. Then, the random walk with restart mechanism was used to calculate vertex intimacy matrices for matched communities across adjacent temporal snapshots, effectively capturing variations in internal connectivity and interaction intensity. Finally, the Matusita distance between the vertex intimacy matrices was calculated, and the evolutionary patterns exceeding a given threshold were identified as anomalies. Experimental results on simulated data and a real-world case study in Beijing demonstrate that AEP-RWR outperforms existing methods in detecting stable communities and accurately capturing microstructure perception. The AEP-RWR method can effectively detect abnormal evolution patterns affected by factors such as road conditions, weather, festivals, and social events, offering valuable insights for urban traffic optimization, safety monitoring, and policy development.