Anomaly Detection in Real-World Temporal Networks
Pablo Moriano, Indiana University-Bloomington
Detection of security threats relies on the ability to collect, filter, and analyze diverse types of security data. Interactions derived from such data are usually modeled as networks aiming to provide a better understanding of the structure and dynamics of the underlying systems. Considering the temporal evolution of these networks is crucial to provide a more detailed characterization of the system’s function. Irregularities, i.e., anomalies, in the general evolution of these networks are usually associated with critical and often undesired behavior. Anomaly detection techniques define the regular behavior of a system, against which unusual patterns are evaluated. Characterizing regular behavior is often a prerequisite to identify these anomalies. However, variations in the volume of interactions during a system’s evolution under particular circumstances may be the norm. Identifying which stationary trends allow us to design reliable detection algorithms remains an open challenge. In this dissertation, we develop novel methods and tools for understanding and identifying anomalies in temporal networks. In particular, we focus on: (i) Graph mining: We show that surprising patterns about the composition of the community structure and k-shell decomposition of the graphs can be leveraged to detect anomalies; (ii) Graph robustness: We show how community detection-based methods are less biased against the density of edges in the system, providing a robust approach to detect anomalous behavior; (iii) Graph anomaly detection: We develop methods for detecting anomalies in different real-world scenarios, including (a) email interactions, (b) social media reaction to catastrophic events, (c) Internet route hijacking, and (d) user-system interactions in control version systems.