Statistical Detection of Network-Level Outliers

• Activity Number: 56
• Type: Invited
• Date/Time: Sunday, August 4, 2013 : 4:00 PM to 5:50 PM
• Sponsor: WNAR
• Author(s): Jennifer Neville*+
• Companies: Purdue University
• Keywords: Social network ; Graph models ; Anomaly detection

Abstract

To date, most of the research on outlier detection for networks has focused on identifying anomalous nodes, links, or small subgraphs in static networks. In dynamic network data, research has focused on detecting outlier links and anomalous network evolution. However, to our knowledge, there are few algorithms that can identify network-level anomalies in large-scale static networks. This is due to the difficulty of obtaining a set of networks to use for learning statical models of normal behavior, coupled with model limitations that make it difficult to capture natural variations in the population. However, our recent work on mixed Kronecker Product Graph Models (mKPGMs) provides a statistical model that is capable of learning accurate models of network populations. Using this approach, we propose a novel outlier detection method to identify anomalous networks using a model-based approach that can learn the underlying distribution of the data from a single network. We illustrate the strengths of our algorithm using synthetic and real world network datasets, showing that the majority of outliers are detected using only a single network as training data.