DIMACS/CCICADA Student-organized Seminar Series

Title: A Streaming Model for Anomaly Detection in Communication Networks: A Renewal Theory Approach

Speaker: Brian Thompson, Rutgers University

Date: Tuesday, November 2, 2010; 12:00-1:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


Any medium for human interaction (e.g. email, phone, face-to-face encounters, IP connections) can be modeled by a network graph, where nodes represent people or computers, and an edge signifies a relationship between two entities. However, communication networks are characterized by their highly dynamic nature - that Alice and Bob are friends says nothing about the frequency or regularity of their communication. Analyzing communication patterns across a network should therefore take into account not just the graph structure, but also a wealth of temporal information.

In this work, we first build a stochastic model for the system based on temporal communication patterns across each edge. We then perform statistical analysis to quantitatively measure the degree of anomaly in an arbitrary subgraph. Finally, we develop graph algorithms to efficiently identify subgraphs with the most anomalous behavior. Experiments on a variety of real-world datasets show the effectiveness and scalability of our approach, as well as a clear and intuitive visual interface.