DIMACS - Graduate Student Combinatorics Seminar

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

Speaker: Brian Thompson, Rutgers University

Date: Wednesday, November 10, 2010 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


Being a mathematician in a Computer Science department with a DHS fellowship poses an interesting research challenge: How can I still do math but get the Department of Homeland Security to fund me? Fortunately, many real-world security problems can be framed using mathematical constructs.

Any type of human interaction (e.g. email, phone, face-to-face encounters, internet connections) can be modeled by a network graph, where vertices represent people or computers, and an edge signifies a relationship such as "friends". However, communication networks have a highly dynamic nature ? that Alice and Bob are friends says nothing about the frequency or regularity of their communication. To analyze communication in a network, we first build a stochastic model based on temporal patterns across each edge, using tools from Renewal Theory. With a little help from statistics, we then define a quantitative measure of "anomaly" in an arbitrary subgraph. Finally, we develop graph algorithms to efficiently identify subgraphs with the most anomalous behavior.