Changes in the structure of observed social and complex networks' structure can indicate a significant underlying change in an organization, or reflect the response of the network to an external event. Automatic detection of change points in evolving networks is rudimentary to the research and the understanding of the effect of such events on networks. Here we present an easy-to-implement and fast framework for change point detection in temporal evolving networks. Unlike previous approaches, our method is size agnostic, and does not require either prior knowledge about the network's size and structure, nor does it require obtaining historical information or nodal identities over time. We use both synthetic data derived from dynamic models and two real datasets: Enron email exchange and Ask-Ubuntu forum. Our framework succeeds with both precision and recall and outperforms previous solutions
@cite_35: Interactions among people or objects are often dynamic in nature and can be represented as a sequence of networks, each providing a snapshot of the interactions over a brief period of time. An important task in analyzing such evolving networks is change-point detection, in which we both identify the times at which the large-scale pattern of interactions changes fundamentally and quantify how large and what kind of change occurred. Here, we formalize for the first time the network change-point detection problem within an online probabilistic learning framework and introduce a method that can reliably solve it. This method combines a generalized hierarchical random graph model with a Bayesian hypothesis test to quantitatively determine if, when, and precisely how a change point has occurred. We analyze the detectability of our method using synthetic data with known change points of different types and magnitudes, and show that this method is more accurate than several previously used alternatives. Applied to two high-resolution evolving social networks, this method identifies a sequence of change points that align with known external "shocks" to these networks.
@cite_26: Detecting anomalies in data is a vital task, with numerous high-impact applications in areas such as security, finance, health care, and law enforcement. While numerous techniques have been developed in past years for spotting outliers and anomalies in unstructured collections of multi-dimensional points, with graph data becoming ubiquitous, techniques for structured graph data have been of focus recently. As objects in graphs have long-range correlations, a suite of novel technology has been developed for anomaly detection in graph data. This survey aims to provide a general, comprehensive, and structured overview of the state-of-the-art methods for anomaly detection in data represented as graphs. As a key contribution, we give a general framework for the algorithms categorized under various settings: unsupervised versus (semi-)supervised approaches, for static versus dynamic graphs, for attributed versus plain graphs. We highlight the effectiveness, scalability, generality, and robustness aspects of the methods. What is more, we stress the importance of anomaly attribution and highlight the major techniques that facilitate digging out the root cause, or the why', of the detected anomalies for further analysis and sense-making. Finally, we present several real-world applications of graph-based anomaly detection in diverse domains, including financial, auction, computer traffic, and social networks. We conclude our survey with a discussion on open theoretical and practical challenges in the field.
@cite_22: This paper addresses the issue of unsupervised network anomaly detection. In recent years, networks have played more and more critical roles. Since their outages cause serious economic losses, it is quite significant to monitor their changes over time and to detect anomalies as early as possible. In this paper, we specifically focus on the management of the whole network. In it, it is important to detect anomalies which make great impact on the whole network, and the other local anomalies should be ignored. Further, when we detect the former anomalies, it is required to localize nodes responsible for them. It is challenging to simultaneously perform the above two tasks taking into account the nonstationarity and strong correlations between nodes. We propose a network anomaly detection method which resolves the above two tasks in a unified way. The key ideas of the method are: (1)construction of quantities representing feature of a whole network and each node from the same input based on eigen equation compression, and (2)incremental anomalousness scoring based on learning the probability distribution of the quantities. We demonstrate through the experimental results using two benchmark data sets and a simulation data set that anomalies of a whole network and nodes responsible for them can be detected by the proposed method.
@cite_7: Abstract : Changes in observed social networks may signal an underlying change within an organization, and may even predict significant events or behaviors. The breakdown of a team's effectiveness, the emergence of informal leaders, or the preparation of an attack by a clandestine network may all be associated with changes in the patterns of interactions among group members. The ability to systematically, statistically, effectively and efficiently detect these changes has the potential to enable the anticipation, early warning, and faster response to both positive and negative organizational activities. By applying statistical process control techniques to social networks we can rapidly detect changes in these networks. Herein we describe this methodology and then illustrate it using four data sets. We nominate four types of dynamic network behaviors for investigation in this paper. These behaviors are not comprehensive; however, it is necessary to define a set of behaviors to focus our investigation of network change. The four behaviors we focus on are network stability, endogenous change, exogenous change, and initiated change. The first data set is the Newcomb fraternity data. The second set of data was collected on a group of mid-career U.S. Army officers in a week-long training exercise. The third data set contains the perceived connections among members of al Qaeda based on open sources, and the fourth data set is simulated using multiagent simulation. The results indicate that this methodology is able to detect change even with the high levels of uncertainty inherent in these data sets.
@cite_8: We introduce a theory of scan statistics on graphs and apply the ideas to the problem of anomaly detection in a time series of Enron email graphs.
@cite_19: 
@cite_23: Outlier (or anomaly) detection is a very broad field which has been studied in the context of a large number of research areas like statistics, data mining, sensor networks, environmental science, distributed systems, spatio-temporal mining, etc. Initial research in outlier detection focused on time series-based outliers (in statistics). Since then, outlier detection has been studied on a large variety of data types including high-dimensional data, uncertain data, stream data, network data, time series data, spatial data, and spatio-temporal data. While there have been many tutorials and surveys for general outlier detection, we focus on outlier detection for temporal data in this book. A large number of applications generate temporal datasets. For example, in our everyday life, various kinds of records like credit, personnel, financial, judicial, medical, etc., are all temporal. This stresses the need for an organized and detailed study of outliers with respect to such temporal data. In the past decade, there has been a lot of research on various forms of temporal data including consecutive data snapshots, series of data snapshots and data streams. Besides the initial work on time series, researchers have focused on rich forms of data including multiple data streams, spatio-temporal data, network data, community distribution data, etc. Compared to general outlier detection, techniques for temporal outlier detection are very different. In this book, we will present an organized picture of both recent and past research in temporal outlier detection. We start with the basics and then ramp up the reader to the main ideas in state-of-the-art outlier detection techniques. We motivate the importance of temporal outlier detection and brief the challenges beyond usual outlier detection. Then, we list down a taxonomy of proposed techniques for temporal outlier detection. Such techniques broadly include statistical techniques (like AR models, Markov models, histograms, neural networks), distance- and density-based approaches, grouping-based approaches (clustering, community detection), network-based approaches, and spatio-temporal outlier detection approaches. We summarize by presenting a wide collection of applications where temporal outlier detection techniques have been applied to discover interesting outliers.
@cite_15: Statistical process control (SPC) requires statistical methodologies that detect changes in the pattern of data over time. The common methodologies, such as Shewhart, cumulative sum (cusum), and exponentially weighted moving average (EWMA) charting, require the in-control values of the process parameters, but these are rarely known accurately. Using estimated parameters, the run length behavior changes randomly from one realization to another, making it impossible to control the run length behavior of any particular chart. A suitable methodology for detecting and diagnosing step changes based on imperfect process knowledge is the unknown-parameter changepoint formulation. Long recognized as a Phase I analysis tool, we argue that it is also highly effective in allowing the user to progress seamlessly from the start of Phase I data gathering through Phase II SPC monitoring. Despite not requiring specification of the post-change process parameter values, its performance is never far short of that of the optimal cusum chart which requires this knowledge, and it is far superior for shifts away from the cusum shift for which the cusum chart is optimal. As another benefit, while changepoint methods are designed for step changes that persist, they are also competitive with the Shewhart chart, the chart of choice for isolated non-sustained special causes.
In stochastic models of networks, change points are points in time where a change in the system's norm is detected in a manner that can be significantly differentiated from plain stochastic noise @cite_35 @cite_19 @cite_22 @cite_23 @cite_26 . McCulloh & Carley @cite_7 convert the series of networks to a time series of scalar values for different network measures, and looked for a stable change in these values (as opposed to temporal change, when looking for anomaly detection) using process mining techniques for change points detection @cite_15 @cite_8 @cite_7 . Change point detection frameworks @cite_26 commonly consist of three phases: (1) generate longitudinal graphs; (2) capture representative features of each graph; (3) detect significant distance between graph snapshots, or window of snapshots, to specify changes.