Authors: C. David Emele, Vitalij Spakov, Wei Pang, Jone Bone, George Coghill (University of Aberdeen, UK)
Abstract
Detecting anomalies in unregulated online spaces like Twitter is challenging due to the lack of ground truth and the transient nature of user behavior. This paper presents ADOVA, a prototype system that utilizes evolutionary clustering to identify outliers. By balancing historical consistency with current data trends, the system adapts to shifting "normal" behaviors, providing a robust framework for unsupervised anomaly discovery in high-velocity social media environments.
Introduction
Detecting anomalies—such as outliers or suspicious behavior—in online and virtual spaces is notoriously difficult. Unlike controlled corporate networks or physical manufacturing lines, online communities are "ad-hoc" and largely unregulated. The authors identify three primary challenges: a lack of ground truth for "normal" behavior, the transience of users within volatile network structures, and the sheer volume and heterogeneity of social media data. Traditional anomaly detection tools, designed for static settings, struggle when the baseline for "normal" shifts rapidly. ADOVA aims to bridge this gap using a clustering mechanism that incorporates temporal history.
Methods: Evolutionary Clustering
The core of ADOVA is the application of Evolutionary Clustering. Unlike standard K-Means, which treats each data snapshot independently, evolutionary clustering seeks a balance between current data and historical patterns. The approach involves two key components:
- Consistency Maintenance: When new data arrives at timestep $t$, the algorithm attempts to match new clusters with those from $t-1$ rather than re-clustering from scratch.
- Centre Recalculation Function: A user-defined change parameter ($cp$) (between 0 and 1) acts as a dial to prioritize either historical consistency or current data trends. Additionally, a relative cluster size ($\gamma$) weight ensures that sudden, small bursts of data do not disproportionately skew the established baseline.
Experimental Setup
The prototype was tested using Twitter data related to the 2014 Scottish Independence referendum (#indyref). The researchers collected 10,000 timestamped tweets between March 9th and March 25th, 2015. For this study, the number of retweets served as the primary metric for clustering interactions.
Results
Qualitative analysis of the #indyref data demonstrated the effectiveness of the evolutionary approach. As the algorithm processed successive timesteps, patterns began to stabilize.
By the ninth timestep, four distinct clusters had emerged, representing the "normal" interaction patterns within the community. Anomalies were clearly visible as data points that failed to fit into any established cluster. These outliers represent tweets or users whose interaction patterns—specifically the relationship between retweet velocity and score—deviated significantly from the community norms.
The evolutionary clustering provided smoother and more natural transitions as new information arrived, making the system robust against momentary noise spikes.
Conclusion and Future Work
ADOVA demonstrates that evolutionary clustering is a robust framework for anomaly detection in unregulated spaces. By autonomously discovering "normal" groups without labeled data, it highlights potential anomalies effectively. Future work will focus on increasing feature depth beyond retweet counts, establishing quantitative benchmarks (e.g., Precision/Recall), and evaluating the computational scalability of the algorithm for processing millions of tweets in real-time.
Summary updated