A Survey on Social Media Anomaly Detection <s> Activity-based Point Anomaly Detection <s> This statistical method can compare in real time the sequence of commands given by each user to a profile of that user’s past behavior. We use a Bayes Factor statistic to test the null hypothesis that the observed command transition probabilities come from a profiled transition matrix. The alternative hypothesis is formed as a Dirichlet mixture of multinomial command probabilities. Based on a population of research users on a single computer, data from some users are inserted into the histories of other users to simulate intrusions. The Bayes factor based on the observation of a block of 100 commands had a false alarm rate of about 6.6% while detecting about 78% of blocks from simulated intrusions. We integrate the test into a detection scheme using control charts. <s> BIB001 </s> A Survey on Social Media Anomaly Detection <s> Activity-based Point Anomaly Detection <s> A hybrid model based mostly on a high-order Markov chain and occasionally on a statistical-independence model is proposed for profiling command sequences of a computer user in order to identify a “signature behavior” for that user. Based on the model, an estimation procedure for such a signature behavior driven by maximum likelihood (ML) considerations is devised. The formal ML estimates are numerically intractable, but the ML-optimization problem can be substituted by a linear inverse problem with positivity constraint (LININPOS), for which the EM algorithm can be used as an equation solver to produce an approximate ML-estimate. The intrusion detection system works by comparing a user's command sequence to the user's and others' estimated signature behaviors in real time through statistical hypothesis testing. A form of likelihood-ratio test is used to detect if a given sequence of commands is from the proclaimed user, with the alternative hypothesis being a masquerader user. Applying the model to real-l... <s> BIB002 </s> A Survey on Social Media Anomaly Detection <s> Activity-based Point Anomaly Detection <s> .; . .. ... .... .. ......... .... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - - - . .. .... ..... .... .... ..... .... .... ..... ..... .... ..... ..... .... .... ..... .... .... ..... ... :: .... ..... ..... .... ..... ..... .... .... ..... .... .... ..... .... .... ..... .... .... ..... .... .... ..... ..... .... ..... ..... . . . . . . . . . . . . . ......... . . . . . .. . . . ......... . . . . . . . . . . . . . . . . . . . . ....... .. . . . . . . . . . . . :.:.:. :.:.:.: : : : :-: -: :-: : : : : :-: :-:-: :- " .' ' . .." ' .." ' , .' ' , .'.'.'.' -, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . '' . . . . ........ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .:.:.:.:. :.: :-: ::-: :-:-: .. . . . . ... ..... . ..... .... .... ..... .... .... ..... ..... .... ..... ..... .... .... ..... .... .... ..... .... .... ..... ..... .... ..... ..... .... .... ..... .... .... ..... .... .... ..... .... .... ..... .... .... ..... ..... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . <s> BIB003
User activities are widely observed in social media, such as computer log-in/log-off records, HTTP access records, and file access records. Activity-based approaches assume that individuals are marginally independent from each other. The anomalousness of an individual is determined only by his own activities. A large body of literature are in the context of computer intrusion detection study. For example, BIB003 investigates the problem of detecting masquerades who disguise themselves as somebody else on the network. The paper collects user activities by looking at their UNIX commands records and manipulating the data to simulate masquerades. Pioneering work for detecting masquerades fall into the framework of statistical hypothesis testing, e.g. BIB001 BIB002 . Different approaches are proposed including Bayes one-step Markov, hybrid multi-step Markov and compression. Here we omit other simple masquerade detection techniques such as uniqueness of the command as also compared in BIB001 . For Bayes one-step Markov method, it states the null hypothesis as a one-step Markov process and the alternative hypothesis as a Dirichlet distribution. The null hypothesis assumes that the current time command C ut of a user u relates to his previous command C u,t−1 . Mathematically speaking, H 0 : P (C ut = k|C u,t−1 = j) = p ukj , where p ukj is the transition probability from command j to command k for user u. Then the algorithm computes the Bayes factor based on the hypothesis for each userx u and set up a threshold with respect tox u to detect anomalous masquerades. This approach models users independently and ignores the potential relationships among users. As a direct generalization of Bayes one-step Markov, BIB002 builds a user model based on high-order Markov chains: hybrid multi-step Markov. It tests over two hypotheses. H 0 : commands are generated from the hybrid Markov model of u; H 1 : commands are generated from other users. The hybrid multi-step Markov method switches between the Markov model and the independence model. The Markov model assumes that a command depends on a set of previous commands, i.e. where λ and r denotes the initial and transitional probability. For the independence model, it assumes that a user's commands are i.i.d samples from a multinomial distribution. The paper computes the test statistics by combining the statistics from two models. Similar to Bayes one-step Markov, hybrid multi-step Markov method sets up a threshold value on the test statistics to flag anomalies. Hybrid multi-step Markov method is able to capture the longrange dependence of the users' commands. However, it also suffers from higher computational cost. Compression takes a distinctive approach where it defines the anomaly score as the additional compression cost to append the test data to the training data. Formally, the score is x = compress({C, c}) − compress(C), where C is the training data, c is the testing data. The method applies the Lempel-Ziv algorithm for the compression operation. However, it can hardly capture the dependencies in the data instances. [67] proposes probabilistic suffix tree (PST) to mine the outliers in a set of sequences S from an alphabet Σ. It makes Markov assumption on the sequences and encodes the variable length Markov chains with syntax similar to Probabilistic Suffix Automata. In PST, an edge is a symbol in the alphabet and a node is labeled by a string. The probabilistic distribution of each node represents the conditional probability of seeing a symbol right after the string label. An example of such PST is shown in Figure 1 . The algorithm first constructs a PST and then computes a similarity measure score SIM N based on marginal probability of each sequence over the PST. Then it selects the top k sequences with lowest SIM N scores as outliers. Since PST encodes a Markov chain, which has been shown to have certain equivalence to the Hidden Markov model, the outliers detected by PST are similar to those using Markov model testing statistics. Though PST construction and SIM N are relative cheap in computation, one drawback is that PST is pre-computed for a fixed alphabet. Pre-computation makes PST less adaptive to the unseen symbols outside of the alphabet or newly coming sequences, which basically requires recomputing the entire tree. [33] investigates Markov-modulated Poisson process to address the specific problem of event detection on time-series of count data. The algorithm assumes the count at time t, denoted as N (t), is a sum of two additive processes: N (t) = N 0 (t) + N E (t), where N 0 (t) denotes the number of occurrences attributed to the "normal" behavior and N E (t) is the "anomalous" count due to an event at time t. More concretely, the periodic portion of the time series counts can be taken as "normal" behavior while the rare increase in the number of counts can correspond to the "anomalous" behavior. For both processes, the paper develops a hierarchical Bayesian model. In particular, the paper models periodic counting data (i.e. normal behavior) with a Figure 1: An example of PST and pruning it using M inCount or P min. The probability distribution vectors are shown on the top of the nodes, and the label strings, the number of times they appear in the dataset and their empirical probability are shown within the nodes The node also records a probability distribution vector of the symbols, which corresponds to the conditional probabilities of seeing a symbol right after the label string in the dataset. For example, the probability vector for the node labelled bba is (0.947,0.053). This means the conditional probability of seeing a right after bba (P (a|bba)) is 0.947, and seeing b right after bba (P (b|bba)) is 0.053. The structure of PST is similar to the classical suffix tree (ST). However, there are some important differences. Besides keeping a probability distribution vector at each node, in a PST, the parent of a node is a suffix of the node, while in a classical ST the parent of a node is a prefix of the node.