Anomaly Detection in Random Graphs Evolving by Preferential Attachment

The paper is devoted to the anomaly detection in directed random graphs that may contain nodes with atypical characteristics (outliers). The anomalies may have abnormal distribution that was not yet observed on previous steps of evolution. The random graphs are assumed to be evolving by the linear preferential attachment model. To detect anomalies the extreme value theory is exploited. That is, the generalized Pareto distribution classifier (GPDC) is applied to random graphs. The application of the GPDC to the Flight network is considered. For our statistical analysis, we use two pairs of nodes' characteristics. These are node PageRanks and Max-Linear Models as well as hub weights and authority weights.