A Survey on Social Media Anomaly Detection <s> Computing Probabilities Us <s> Abstract Computer intruders are modern day burglars: some of them steal information, some wreak havoc to the system, some just want to prove they can break in. Computer intrusion detection is concerned with designing alarm systems to prevent break-ins. This paper presents a method for detecting intruders/users masqueradering as other users. We examine UNIX command streams of users and search for anomalies. We identify anomalies based on unpopular and uniquely used commands. <s> BIB001 </s> A Survey on Social Media Anomaly Detection <s> Computing Probabilities Us <s> The mining of outliers (or anomaly detection) in large databases continues to remain an active area of research with many potential applications. Over the last several years many novel methods have been proposed to efficiently and accurately mine for outliers. In this paper we propose a unique approach to mine for sequential outliers using Probabilistic Suffix Trees (PST). The key insight that underpins our work is that we can distinguish outliers from non-outliers by only examining the nodes close to the root of the PST. Thus, if the goal is to just mine outliers, then we can drastically reduce the size of the PST and reduce its construction and query time. In our experiments, we show that on a real data set consisting of protein sequences, by retaining less than 5% of the original PST we can retrieve all the outliers that were reported by the full-sized PST. We also carry out a detailed comparison between two measures of sequence similarity: the normalized probability and the odds and show that while the current research literature in PST favours the odds, for outlier detection it is normalized probability which gives far superior results. We provide an information theoretic argument based on entropy to explain the success of the normalized probability measure. Finally, we describe a more efficient implementation of the PST algorithm, which dramatically reduces its construction time compared to the implementation of Bejerano [3]. <s> BIB002 </s> A Survey on Social Media Anomaly Detection <s> Computing Probabilities Us <s> Networks of various kinds often experience anomalous behaviour. Examples include attacks or large data transfers in IP networks, presence of intruders in distributed video surveillance systems, and an automobile accident or an untimely congestion in a road network. Machine learning techniques enable the development of anomaly detection algorithms that are non-parametric, adaptive to changes in the characteristics of normal behaviour in the relevant network, and portable across applications. In this paper we use two different datasets, pictures of a highway in Quebec taken by a network of webcams and IP traffic statistics from the Abilene network, as examples in demonstrating the applicability of two machine learning algorithms to network anomaly detection. We investigate the use of the block-based One-Class Neighbour Machine and the recursive Kernel-based Online Anomaly Detection algorithms. <s> BIB003 </s> A Survey on Social Media Anomaly Detection <s> Computing Probabilities Us <s> In this paper, we propose examining the participants in various meetings or communications within a social network, and using sequential inference based on these participant lists to quickly and accurately predict anomalies in the content of those communications. The proposed approach consists of two main elements: (1) filtering, or assigning a belief or likelihood to each successive measurement based upon our ability to predict it from previous noisy observations, and (2) hedging, or flagging potential anomalies by comparing the current belief against a time-varying and data-adaptive threshold. The threshold is adjusted based on feedback requested from an expert system. In general, parsing communication data can require nontrivial computational resources, but since parsed data is only used sparingly for feedback, the overall computational complexity of the proposed approach is relatively low. Regret bounds quantify the performance of the proposed approach, and experiments on the Enron email database demonstrate its efficacy. <s> BIB004 </s> A Survey on Social Media Anomaly Detection <s> Computing Probabilities Us <s> We propose a novel approach which combines the use of Bayesian network and probabilistic association rules to discover and explain anomalies in data. The Bayesian network allows us to organize information in order to capture both correlation and causality in the feature space, while the probabilistic association rules have a structure similar to association mining rules. In particular, we focus on two types of rules: (i) low support & high confidence and, (ii) high support & low confidence. New data points which satisfy either one of the two rules conditioned on the Bayesian network are the candidate anomalies. We perform extensive experiments on well-known benchmark data sets and demonstrate that our approach is able to identify anomalies in high precision and recall. Moreover, our approach can be used to discover contextual information from the mined anomalies, which other techniques often fail to do so. <s> BIB005
The probability associated with a seque is P T (s) = P T (s 1 )P T (s 2 |s 1 ) . . . P T (s l | PST allows an efficient computation of ate conditional probability terms. For example let us compute P T ( PST in Figure 1 . The search start and traverse along the path → b → is in the reverse order of string aba stops at the node with label bab, bec longest suffix of abab that can be fou and P T (b|abab) is estimated by P T (b|b we are exploiting the short memory occurs in sequences generated from nat empirical probability distribution of t given the preceding subsequence, can b by observing no more than the last L subsequence  BIB005 . If the PST is pruned using minC search stops at the node with label ab is estimated by P T (b|ab) = 0.394. Th example to compute the probability of the PST pruned using minCount = 25 Since the probabilities are multipli taken to avoid the presence of zero pr a smoothing procedure is employed a of the PST and the probability distr 97 Figure 1 : A example of PST. For each node, top array shows the probability distribution. Inside the node shows the label string, the number of times it appears in the data set and the empirical probability. BIB002 Poisson process and models rare occurrences (i.e. anomaly behavior) via a binary process. The algorithm then uses the MCMC sampling algorithm to infer the posterior marginal distribution over events. It uses the posterior probability as an indicator to automatically detect the presence of unusual events in the observation sequence. The paper applies the model to detect the events from free-way traffic counts and the building access count data. The method takes a full Bayesian approach as a principled way to pose hypothesis testing. However, it treats each time series as independent and fails to consider the scenario where multiple time series are inter-correlated. Another application in social network anomaly detection is proposed in BIB004 . The paper proposes to detect unusual meetings by investigating the presence of meeting participants. Specifically, for each time stamp t = 1, 2, · · · , the inputs are given as a snapshot of the network in the form of a binary string x t = (x t (1), · · · , x t (n)) ∈ {0, 1} n , where x t (j) = 0 or 1 indicates whether the jth person participated in the meeting at time t as well as the feedback from expert system with the correct labels y t ∈ {−1, +1}. The algorithm outputs a binary label for each network stateŷ t ∈ {−1, +1} according to whether or not x t is anomalous. Under the proposed two-stage framework, "filtering stage" estimates the model parameters and updates belief with the new observation. It builds an exponentially model driven by a time-vary parameter and learns the model parameter in an online fashion. "Hedging stage" compares the model likelihood of x t as ζ t with the critical threshold τ t and flag anomalies if ζ t > τ t . After that, the online learning algorithm utilizes the feedback from an expert system to adjust the critical threshold value τ t+1 = argmin τ (τ − τ t − ηy t 1ŷ t =yt ) 2 . It is easy to see from the construction of x t that each person's participation is taken as an independent feature entry. Though this work highlights the network structure, the relational information utilized lies only between people and meetings, without considering the interaction among people themselves. Generally speaking, activity-based approaches model the activity sequence of each user separately under certain Markov assumption. They locate the anomaly by flagging deviations from a user's past history. These approaches provide simple and effective ways to model user activities in a real-time fashion. The models leverage the tool of Bayesian hypothesis testing and detect anomalies that are statistically well-justified. However, as non-parametric methods, Markov models suffer from the rapid explosion in the dimension of the parameter space. The estimation of Markov transition probabilities becomes non-trivial for large scale data set. Furthermore, models for individual normal/abnormal activities are often ad hoc and are hard to generalize. As summarized by BIB001 in his review work on computer intrusion detection: "none of the methods described here could sensibly serve as the sole means of detecting computer intrusion". Therefore, exploration of deeper underlying structure of the data with fast learning algorithms is necessary to the development of the problem. Here we also refer interested readers to more general reviews of computer network anomaly detection BIB003  .