Source-linked AI summary
Anomaly detection in online social networks
David Savage, Xiuzhen Zhang, Xinghuo Yu, Pauline Chou, Qingmai Wang
TL;DR
The paper addresses how to detect irregular, often illegal behaviour in online social networks. It surveys computational techniques and organizes anomalies by their static or dynamic and labelled or unlabelled character. Its central conclusion is that detection depends on both constructing suitable network feature spaces and applying anomaly-classification methods, with feature selection and scalable analysis remaining key challenges.
Problem
Irregular and often illegal behaviour in online social networks motivates a focused survey of anomaly-detection techniques and the problem domains they can address.
Method
The paper surveys existing techniques, characterizes anomalies as static or dynamic and labelled or unlabelled, and examines feature construction and anomaly-detection methods.
Results
The survey finds that anomaly detection separates into selecting and calculating network features and classifying observations in the resulting feature space.
Takeaways & Limitations
Effective social-network anomaly detection requires suitable feature spaces, traditional detection methods once features are available, and scalable solutions for rich feature spaces.
Takeaways & Limitations
The paper excludes horizontal anomalies, which concern entity behaviours that vary across data sources.
Abstract
from arXiv · showhide
Anomalies in online social networks can signify irregular, and often illegal behaviour. Anomalies in online social networks can signify irregular, and often illegal behaviour. Detection of such anomalies has been used to identify malicious individuals, including spammers, sexual predators, and online fraudsters. In this paper we survey existing computational techniques for detecting anomalies in online social networks. We characterise anomalies as being either static or dynamic, and as being labelled or unlabelled, and survey methods for detecting these different types of anomalies. We suggest that the detection of anomalies in online social networks is composed of two sub-processes; the selection and calculation of network features, and the classification of observations from this feature space. In addition, this paper provides an overview of the types of problems that anomaly detection can address and identifies key areas of future research.
1. Introduction
Online social-network anomalies reflect interaction patterns that differ from peers and can reveal malicious or otherwise important participants. This paper surveys detection techniques, applicable problem domains, future challenges, and research priorities.
- 1. Introduction: Anomalous interaction patterns can create unusual network structures, such as highly interconnected groups of collaborating fraudsters.Detection compares observed network structure with an assumed or derived model of normal interaction.
- 1. Introduction: Online social-network anomaly detection has been applied to influential participants, clandestine structures, fraudulent activity, and predatory behaviour.
- 1. Introduction: The paper surveys existing techniques and the problem domains and challenges they address in online social networks.
- 1. Introduction: It also examines future challenges and identifies areas where anomaly detection research can improve social network analysis.
- 1. Introduction: The review targets anomaly-detection tools across social networks rather than particular application domains, with relevant work predominantly published in computer science.
3. Problem domains for the application of anomaly detection in social networks
Anomaly detection addresses malicious, illegal, and socially significant behaviour across online and transaction-derived networks. Applications include spam, predation, fraud, organised crime, terrorism, influence, community roles, and communication patterns.
- 3. Problem domains for the application of anomaly detection in social networks: The paper extends prior general and domain-specific reviews by focusing specifically on anomaly detection in social networks and its associated challenges.
- 3. Problem domains for the application of anomaly detection in social networks: Online social systems expose users to spam, offensive material, and sexual predation, while anonymity and unsupervised interaction can facilitate predator access to vulnerable individuals.
- 3. Problem domains for the application of anomaly detection in social networks: Fraudsters exploit online reputation systems, fake reviews, and anomalous interaction structures to deceive buyers or influence perceptions of product quality.
- 3. Problem domains for the application of anomaly detection in social networks: Anomaly detection in mobile-phone and financial-transaction networks has been used to identify organised criminal behaviour, including insurance fraud and terrorism.
- 3. Problem domains for the application of anomaly detection in social networks: Non-criminal applications include detecting influential individuals, community roles, participation levels, and unusual email-traffic patterns.
4. Definitions
The paper defines network anomalies as interaction patterns that significantly differ from the norm, while emphasizing that both the deviation and its measurement depend on the application domain. Its scope excludes horizontal anomalies across data sources.
- 4. Definitions: Network anomalies are patterns of interaction that significantly differ from the norm.The paper notes that this definition is imprecise because the relevant interaction pattern and deviation depend on the behaviour of interest.
- 4. Definitions: The appropriate anomaly feature may vary by study, such as counting an employee’s emails for one behavioural question and using another metric for a different question.
- 4. Definitions: The review focuses on interaction patterns that differ from normal behaviour within the same social network.
- 4. Definitions: Horizontal anomalies, in which an entity’s behaviour varies by data source, are outside the paper’s scope.The authors suggest that increasingly diverse social-network data sources make this an important area for future research.
- 4. Definitions: Detecting anomalies requires suitable features that separate normal from anomalous behaviour, but selecting those features is itself a key challenge.
5. Characterisation of anomalies
Social-network anomaly analysis centers on interactions represented as graph structure, with networks and anomalies characterized along static–dynamic and labelled–unlabelled dimensions. Representation choices depend on the anomaly of interest and its context.
- 5. Characterisation of anomalies: Social-network analysis studies interactions between individuals and their relationships, unlike non-network analysis that ignores peer interactions.
- 5. Characterisation of anomalies: Networks are represented as graphs whose vertices denote entities and whose edges denote interactions; multi-type entities may require bipartite or higher-order graphs.
- 5. Characterisation of anomalies: Dynamic networks encode changes over time, whereas static representations aggregate interactions across time; labelled networks include node or edge attributes.
- 5. Characterisation of anomalies: Dynamic anomalies are defined relative to previous network behaviour, while static anomalies are defined relative to the remainder of the network.
- 5. Characterisation of anomalies: Anomalies may also be global or local and may concern a minimal anomalous unit ranging from one vertex to a collaborating group.
6. Methods for anomaly detection
The survey organizes anomaly-detection methods primarily by whether anomalies are static or dynamic and labelled or unlabelled. Approaches include structural, signal-processing, information-theoretic, community-contextual, belief-propagation, and scan-statistical methods, with dynamic labelled anomalies least represented.
- The survey finds that static/dynamic and labelled/unlabelled characterizations best differentiate anomaly-detection approaches.Other characteristics include local versus global context and the minimal anomalous unit.
- Static, unlabelled anomalies: Static unlabelled methods detect unusual network structures using ego-net properties, power-law residuals, or signal-processing tests for anomalous subgraphs.Ego-nets contain a subject and immediate neighbours; structural examples include stars, near-stars, and near-cliques.
- Static, labelled anomalies: Label-aware methods use network context, heavy ego-net measurements, or belief propagation to identify anomalous combinations of structures, edge labels, and vertex labels.Belief propagation iteratively updates hidden labels using observed labels in the network.
- Static, unlabelled anomalies: Signal-processing approaches model anomalous subgraphs as signals embedded in background noise and test whether the graph contains such a subgraph.The null hypothesis is that the graph is noise, while the alternative treats it as signal plus noise.
- Static, labelled anomalies: Information-theoretic methods represent interactions as subgraphs and can detect rare complex information flows, including a single unusual forwarded email in the Enron data.The detected pattern involved an email from a director to a non-management employee that was then forwarded to another non-management employee.
- Dynamic anomalies: Scan statistics are the most prominent approach identified, while dynamic labelled anomalies are least represented, with only one surveyed example.The survey also suggests adapting dynamic unlabelled methods to labelled settings because node and edge labels may improve separation of normal and anomalous behaviour.
7. Discussion
The survey organizes online social-network anomaly detection around anomaly type, feature-space construction, and anomaly classification. It identifies feature selection, scalable computation, evaluation, and limited data as central challenges for the field.
- Detection separates into calculating a suitable feature space and identifying anomalies within that space, since the detection method is often independent of anomaly type.The survey illustrates this with regression and nearest-neighbour methods applied to the same extracted feature space.
- A five-step workflow maps the affected unit, expected deviations, and context into measurable properties before calculating distances between observations.The workflow covers nodes, neighbourhoods, communities, and the contextual measurement of deviations.
- Scalable anomaly-detection solutions are important because online social networks are large and feature calculation can be computationally expensive.The survey treats feature-space selection as equally important to scalable calculation.
- Feature-space selection remains difficult because few papers explain the behaviour-to-network-property mapping, while correlated features and restricted comparisons complicate guidance.The authors suggest that guidelines, heuristics, or broader feature-space comparisons could help address this challenge.
- Evaluation is constrained by the lack of publicly available datasets with known ground truths, so many methods are tested on one dataset and manually verified.Existing well-characterized datasets such as Enron are relatively small and suitable for only a subset of problem domains.
- Approaches are categorized by static or dynamic anomalies and labelled or unlabelled observations, with different network features examined for each category.