ADOVA: Anomaly Detection in Online and Virtual spAces

Chukwuemeka David Emele, Vitalij Spakov, Wei Pang, Jone Bone, George M. CoghillCOOS@AAMAS 2015 · OpenReview

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:

  1. 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.
  2. 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.

Initial cluster formation in the early stages of the #indyref dataset analysis.

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.

Emergence of four distinct clusters and visible anomalies by the ninth timestep.

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

BibTeX
@inproceedings{emele2015adova,
  author = {Chukwuemeka David Emele and Vitalij Spakov and Wei Pang and Jone Bone and George M. Coghill},
  title = {{ADOVA: Anomaly Detection in Online and Virtual spAces}},
  booktitle = {COOS@AAMAS},
  year = {2015},
  url = {https://openreview.net/forum?id=1KN91NaYee},
}
Figure