# Outlier Detection and Prediction in Evolving Communities
## 2 Related Work
### Outlier Detection
#### 2.2.1 Static Methods  
With regard to structural static methods, OutRank [21] is an efficient stochastic graph-based outlier detection algorithm. In contrast to our work and other proposed methods, it considers weighted graphs, with each node's weight corresponding to its similarity with other nodes. Using random walks, the algorithm first finds central nodes, then detects outliers based on their similarity with these nodes. OutRank can detect micro-clusters of outliers as well. The authors of [22] achieved significant speedup in their outlier detection technique by introducing permanence as a node-based metric and focusing only on specific groups of nodes that are more likely to be outliers. In a recent paper [23], the fluctuation of a node was introduced as the basis of an outlier factor which, similarly to our outlier score, shows how much a node differentiates from its neighbors. In another static structural outlier detection method, in [24] the authors developed a model to perform anomaly detection in which anomalous edges are identified as those deviating from regular patterns determined by community structure. The model outputs labels for each node, defining regular nodes as legitimate and anomalous nodes as outliers. Similarly to our method, outlier detection is performed simultaneously with community detection, and anomalous edges are not necessarily assessed as undesirable interactions or malicious activity. Regarding content-based outlier detection techniques, Radar [25] is a framework for anomaly detection in networks containing content information. Radar starts from the networks' attributes and detects anomalies based on the residual errors of the instances while trying to optimize the objective function. As the authors mention in their conclusion, however, this method is not yet suitable for online attributed networks. The context of outliers was discussed in [26], where local outliers were based only on a single attribute or a selection of attributes. Similarly to our work, outliers were ranked based on the degree of deviation. However, the considered attributes were only numeric, while we focus on labels generated by the nodes' attributes. Moreover, instead of selecting a set of interesting attributes, we consider a node's outlierness to be influenced by all its labels and its structural properties, allowing for leveraging between the two. Finally, considering hybrid static methods, the authors of [27] grouped outliers into two basic categories, namely, structural and contextual. Structural outliers were defined based on their connections, while contextual outliers were those with attributes differing significantly from their neighboring nodes. The authors benchmarked different algorithms in order to assess how the different detection methods responded to the two types of outliers in static graphs. Non-overlapping groups were required during the community formation procedure. In [28], the authors proposed a method for outlier detection in multi-view systems; initially, they categorized outliers as class outliers, equivalent to to structure-based outliers, and attribute outliers, equivalent to content-based ones. They additionally proposed a mixed type of outliers, class-attribute outliers. In our approach, instead of separating outliers into structural- and content-based groups, we consider both criteria at the same time, thereby creating a more complete view of a node's behavior. The use of the weighting factor between structural and content criteria enables us to focussolely on content or structure as required, or to assign more importance to one over the other as necessary. Finally, in [29], anomaly detection was performed in social graphs based on anomaly scoring, which consisted of a structure-based score and an attributed-based score, quite similar to the outlier score that we propose. First, modularity-based community detection was performed; then, in a second phase, each node was ranked with an anomaly score.