A Survey on Social Media Anomaly Detection <s> Dynamic Graph <s> We report on an automated runtime anomaly detection method at the application layer of multi-node computer systems. Although several network management systems are available in the market, none of them have sufficient capabilities to detect faults in multi-tier Web-based systems with redundancy. We model a Web-based system as a weighted graph, where each node represents a "service" and each edge represents a dependency between services. Since the edge weights vary greatly over time, the problem we address is that of anomaly detection from a time sequence of graphs.In our method, we first extract a feature vector from the adjacency matrix that represents the activities of all of the services. The heart of our method is to use the principal eigenvector of the eigenclusters of the graph. Then we derive a probability distribution for an anomaly measure defined for a time-series of directional data derived from the graph sequence. Given a critical probability, the threshold value is adaptively updated using a novel online algorithm.We demonstrate that a fault in a Web application can be automatically detected and the faulty services are identified without using detailed knowledge of the behavior of the system. <s> BIB001 </s> A Survey on Social Media Anomaly Detection <s> Dynamic Graph <s> How can we find communities in dynamic networks of socialinteractions, such as who calls whom, who emails whom, or who sells to whom? How can we spot discontinuity time-points in such streams of graphs, in an on-line, any-time fashion? We propose GraphScope, that addresses both problems, using information theoretic principles. Contrary to the majority of earlier methods, it needs no user-defined parameters. Moreover, it is designed to operate on large graphs, in a streaming fashion. We demonstrate the efficiency and effectiveness of our GraphScope on real datasets from several diverse domains. In all cases it produces meaningful time-evolving patterns that agree with human intuition. <s> BIB002 </s> A Survey on Social Media Anomaly Detection <s> Dynamic Graph <s> Given an author-conference network that evolves over time, which are the conferences that a given author is most closely related with, and how do they change over time? Large time-evolving bipartite graphs appear in many settings, such as social networks, co-citations, market-basket analysis, and collaborative filtering. Our goal is to monitor (i) the centrality of an individual node (e.g., who are the most important authors?); and (ii) the proximity of two nodes or sets of nodes (e.g., who are the most important authors with respect to a particular conference?) Moreover, we want to do this efficiently and incrementally, and to provide “any-time” answers. We propose pTrack and cTrack, which are based on random walk with restart, and use powerful matrix tools. Experiments on real data show that our methods are effective and efficient: the mining results agree with intuition; and we achieve up to 15∼176 times speed-up, without any quality loss. <s> BIB003 </s> A Survey on Social Media Anomaly Detection <s> Dynamic Graph <s> Graphs are popularly used to model structural relationships between objects. In many application domains such as social networks, sensor networks and telecommunication, graphs evolve over time. In this paper, we study a new problem of discovering the subgraphs that exhibit significant changes in evolving graphs. This problem is challenging since it is hard to define changing regions that are closely related to the actual changes (i.e., additions/deletions of edges/nodes) in graphs. We formalize the problem, and design an efficient algorithm that is able to identify the changing subgraphs incrementally. Our experimental results on real datasets show that our solution is very efficient and the resultant subgraphs are of high quality. <s> BIB004 </s> A Survey on Social Media Anomaly Detection <s> Dynamic Graph <s> Information networks, such as social networks and that extracted from bibliographic data, are changing dynamically over time. It is crucial to discover time-evolving communities in dynamic networks. In this paper, we study the problem of finding time-evolving communities such that each community freely forms, evolves, and dissolves for any time period. Although the previous t -partite graph based methods are quite effective for discovering such communities from large-scale dynamic networks, they have some weak points such as finding only stable clusters of single path type and not being scalable w.r.t. the time period. We propose CHRONICLE , an efficient clustering algorithm that discovers not only clusters of single path type but also clusters of path group type. In order to find clusters of both types and also control the dynamicity of clusters, CHRONICLE performs the two-stage density-based clustering, which performs the 2nd-stage density-based clustering for the t -partite graph constructed from the 1st-stage density-based clustering result for each timestamp network. For a given data set, CHRONICLE finds all clusters in a fixed time by using a fixed amount of memory, regardless of the number of clusters and the length of clusters. Experimental results using real data sets show that CHRONICLE finds a wider range of clusters in a shorter time with a much smaller amount of memory than the previous method. <s> BIB005 </s> A Survey on Social Media Anomaly Detection <s> Dynamic Graph <s> Traditional anomaly detection on social media mostly focuses on individual point anomalies while anomalous phenomena usually occur in groups. Therefore it is valuable to study the collective behavior of individuals and detect group anomalies. Existing group anomaly detection approaches rely on the assumption that the groups are known, which can hardly be true in real world social media applications. In this paper, we take a generative approach by proposing a hierarchical Bayes model: Group Latent Anomaly Detection (GLAD) model. GLAD takes both pair-wise and point-wise data as input, automatically infers the groups and detects group anomalies simultaneously. To account for the dynamic properties of the social media data, we further generalize GLAD to its dynamic extension d-GLAD. We conduct extensive experiments to evaluate our models on both synthetic and real world datasets. The empirical results demonstrate that our approach is effective and robust in discovering latent groups and detecting group anomalies. <s> BIB006
Social networks are dynamic in nature. Therefore, it is worthwhile to consider the problem of anomaly detection in a dynamic setting. A brief survey on dynamic network anomaly detection is elaborated in  . The survey characterizes the techniques employed for the problem into three groups: Time Series Analysis of Graph Data, Anomaly Detection using Minimum Description Length, Window Based Approaches. Based on this categorization, we review those anomaly detection approaches that incorporate the network dynamics into their models. Dynamic networks can be represented as a time series of graphs. A common practice is to construct a time series from the graph observations or substructures.  uses a number of graph topology distance measures to quantify the differences between two consecutive networks, such as weight, edge, vertex, and diameter. For each of these graph topology distance measures, a time series of changes is constructed by comparing the graph for a given period with the graph(s) from one or more previous periods. Given a graph G = {V, E, W V , W E }, the algorithm constructs a time series of changes for each graph topology distance measures. Each time series is individually modeled by an ARMA process. The anomaly is defined as days with residuals of more than two standard errors from the best ARMA model. The paper detects anomalies by setting up a residual threshold for the goodness of model fitting for time series. The proposed method in  is designed for change point detection. The performance of the proposed algorithm highly depends on how the graph topology distance measures are defined. Additionally, the distance measure is only able to capture the correlation between two consecutive time stamps rather than long-range dependencies. Graph eigenvectors of the adjacency matrices is another form of the time series extracted from dynamic graph streams. In BIB001 , the paper addresses the problem of anomaly detection in computer systems. Assume a system has N services, the paper defines a time evolving dependency matrix D ∈ R N ×N , where each element of the matrix D i,j is a function value relate to the number of service i's requests for service j within a pre-determined time interval. Given a time series of dependency matrices D(t), the algorithm extracts the principal eigenvector u(t) of D(t) as the "activity" vector, which can be interpreted as the distribution of the probability that a service is holding the control token of the system at a virtual time point. To detect anomalies, the authors define the typical pattern as a linear combination of the past activity vectors r(t) = c i=1 W v i u(t − i + 1), where {v i } are the coefficients and c is the normalization constant. Then the algorithm calculates the dissimilarity of the present activity vector from this typical pattern. The anomaly metric z(t) is defined as z(t) = 1 − r(t − 1) T u(t). When the anomaly metric quantity z(t) is greater than a given threshold, the system flags anomalous situation. Compared with representing graphs with edges, weights and vertices as in  , features built upon eigenvectors capture the underlying invariant characteristics of the system and preserve good properties such as positivity, non-degeneracy, etc. Besides time series analysis of the graph stream, Minimum description length (MDL) has been applied to anomaly detection as another way of characterizing the dynamic networks. BIB002 detects the change points in a stream of graph series. It introduces the concept of graph segment, which is one or more graph snapshots and the concept of source/destination partitions, which groups the source and destination nodes into clusters. Figure 3 illustrates those concepts in a three graph series. The rational behind the algorithm is to consider whether it is easier to include a new graph into the current graph segment or to start a new graph segment. If a new graph segment is created, it is treated as a change point. Given current graph segment G (s) , encoding cost c o and a new graph G (t) , the algorithm computes the encoding cost for G (s) {G (t) } as c n and G (t) as c. If c n − c o < c, the new graph is included in the current segment. Otherwise, {G (t) } forms a new stream segment and time t is a change point. To compute the encoding cost of a graph segment, the algorithm tries to partition the nodes in a segment into source and destination nodes so that the MDL for encoding the partitions is minimized. In this case, a change point indicates the time when the structure of the graph has dramatically changed. One limitation of this algorithm is that it can only handle unweighted graphs, which cannot encode the intensity of the communication between users. Thus, this method does not fit the situation when the communications of people suddenly increase while the topological structure stays unchanged. (e.g. a heated discussion starting to prevail in a social network). is between (i) the number of bits needed to describe the communities (or, partitions) and their change points (or, segments) and (ii) the number of bits needed to describe the individual edges in the stream, given this information. We begin by first assuming that the change-points as well the source and destination partitions for each graph segment are given, and we show how to estimate the bit cost to describe the individual edges (part (ii) above). Next, we show how to incorporate the partitions and segments into an encoding of the entire stream (part (i) above). Evolving networks can also provide insights into the temporal changes of groups. Detecting anomalously groups in dynamic graphs is more challenging, as the group structures are not fixed and the unusual patterns in the group can also change. [25] take a bipartite graph of individual entities and sequential ordered attributes as inputs and returns a group of entities whose attributes sequences are less likely to be generated from the proposed Markov chain model. One example of this type of anomaly is that several people constantly jump from companies to companies together. They track the complete history of employments and disclosures, and recognize the tribes that are closely related. Formally, the method requires bipartitie graph G = (R A, E), where R = {r i } is the entity representatives, A = {a j } is the attributes and E are edges with time interval annotation. For each edge e ∈ E, e = (r i , a j , tstart ij , tend ij ). The method begins by listing the co-worker relationships in the graph. Every pair f ij = (r i , r j ) indicates the individuals that have worked together. This results in a new graph H = (R, F ), where edges in the new graph F = {f ij } is annotated with individuals attribute and history information. Then the paper defines a significance score for each edge, which measures the significance or the anomalousness of shared jobs. The algorithm proceeds by identifying significant edges and computing the significance score c for each of them. Then the proposed method picks a threshold d for the scores and prune all the edges f ij for c ij < d. After pruning, the connected components in the remaining graph (which should be quite sparse after the pruning) are regarded as anomalous groups, or tribes as referred in the paper. As also pointed by authors, the choice of scoring pairs constitutes the heart of the problem, thus posing difficulty in the selection BIB003 directly analyze graph structures and efficiently track node proximity, which measures the relevance between two nodes in bipartite graphs. The paper defines a dynamic proximity score based on the probability to "random walk" from one to the other in the static graph. Low proximity to other nodes can in a way indicate anomaly. Their definition of dynamic proximity accounts for two important aspects of node relevance: proximity involves multiple snapshots of the graph; proximity does not drop over time. BIB003 extends this method to track anomalous nodes in time evolving graphs by defining a dynamic proximity metric. This dynamic proximity is derived from the edge and weight differences between graph snapshots and preserves a monotonicity property. [ BIB004 proposes to detect the significant changing subgraphs. Given two consecutive snapshots of a graph G i−1 and G i , the algorithm defines an importance score to measure the accumulative change of a node's closeness to its l-step neighbors (neighbors within l hops from the node) between two consecutive graph slices. In their context, random walk with restart is used to model the node relevance. The closeness of a pair of vertices v j and v k is defined as , where τ is a path from v j to v k whose length is length(τ ) with transition probability p(τ ). The importance score is therefore the summation of the closeness changes of v j to the other nodes, defined as Note that two consecutive graph slices G i and G i+1 have the same set of nodes, but their edge set could be different. With the node closeness Π l i and the vertex importance score V I, the paper uses a strategy similar to density clustering to detect the significant subgraphs. Specifically, the algorithm puts the most important node in the current subgraph g, adds all of its l-step neighbors to a max-heap. As long as there exists a node whose closeness with node t exceeds certain threshold, the algorithm iteratively moves t from the heap into g. When the iteration terminates, g is regarded as the anomalous subgraph, and the algorithm proceeds to generate anomalous subgraphs for the next timestamp. The proposed algorithm detects subgraphs with significant change in edges as group anomalies. The incremental learning of nodes closeness changes makes the algorithm quite efficiently. However, the output subgraphs heavily rely on the threshold for the closeness, and there is no clear mapping between the nodes' closeness and anomalousness. In another work which tries to detect changing communities by BIB005 , the authors propose a two-stage density-based clustering algorithm CHRONICLE. The algorithm first clusters nodes in each snapshot graph G i at time T i using structural similarity σ, defined as σ(v, w) = , where N (v) is the neighborhood nodes of v. Then the algorithm replaces each cluster with one node to form a t-partite graph, as shown in Fig. 6 . In the t-partite graph, the edge weight between two nodes (dashed edges in Fig. 6 ) within a time stamp T i denotes the number of edges between the two clusters, and the edge weight between two nodes from two consecutive time stamps is defined as the Jaccard similarity between the node sets of two clusters. In the second stage, SCAN is applied again on the t-partite graph. In Fig. 6 different colors represents different clusters in the t-partite graph. From these clusters we can clearly monitor the formation and dissolving of the groups, which could provide some hint on which groups are anomalously changing. However, the algorithm is originally designed for monitoring community evolution instead of anomalous changing group detection. It is not clear how the algorithm can be adapted for anomaly detection yet. [30] also presents a two-stage method, which combines the Bayesian approach for discrete activity modeling with the graph analysis techniques for discovering anomalous structures. In .g., c 13 c 23 c 33 ) are not so high. Here, () represents a consolidation of multiple local clusters. We call a cluster of this type as a path group cluster since there are multiple paths over time in the cluster. The BFS cannot find the clusters of this type. In this paper, we propose a density-based clustering algorithm, CHRONI-CLE, that efficiently discovers both single path clusters and path group clusters. For finding clusters of both types, CHRONICLE performs the density-based clustering in two stages: the 1st-stage density-based clustering for each timestamp network and the 2nd-stage density-based clustering for the t-partite graph. In case of the previous BFS method, it only performs the 1st-stage clustering and finds single path clusters by using a DP algorithm. A density-based clustering approach has several advantages such as discovering clusters of arbitrary shape, handling noise, and being fast. These features allow us to find a wider range of clusters (i.e., not only single path clusters, but also path group clusters) in an efficient way. As the length of dynamic networks, the number of clusters, or the length of cluster (i.e., path length) increases, the running time and the amount of memory usage of the BFS method largely increase. Using disk for sav- Figure 6 : An example of t-partite graph constructed from a dynamic network (taken from BIB005 ). Each circle at a time stamp T i represents a cluster in the snapshot graph G i . the first stage identifies potentially anomalous nodes by conjugating Bayesian models for discrete time counting processes. Specifically, it models the number of communications made from i to j up until discrete time t denoted by N ij (t) as a counting process. It learns the distributions of the counts and use predictive p-value to evaluate the new observations for anomalous nodes. In the second stage, standard network inference tools are applied to the reduced subnetwork of the anomalous nodes identified from the first stage to uncover anomalous structure. Simulated cell phone communication as well as real-time press and media summary data are investigated to validate the method. This approach does not distinguish between point anomaly and group anomaly, hence hard to evaluate. To further account for the dynamic nature of social media, BIB006 generalizes GLAD to the d-GLAD model as an extension for handling time series and formulate the problem as a change point detection task. The paper models the temporal evolution of the role mixture rate for each group with a series of multivariate Gaussian distributions. At a particular time point, the Gaussian has its mean as the value of the mixture rate. And the mixture rate of the next time point is a normalized sample from this Gaussian distribution. Since the model requires the mixture rate to be the parameters of a multivariate distribution over features, the authors apply a soft-max function to normalize the sample drawn from the multivariate Gaussian. The soft-max function is defined as S(θ m ) = exp θm m exp θm . When the total time length T equals one, d-GLAD reduces to the GLAD model. Figure 7 depicts the probabilistic graphical model of d-GLAD. The model is demonstrated successful in detecting change in topics of the scientific publications and party affiliation shift of US senators.