2007 Conference on Interdisciplinary Studies in Information Privacy and Security May 22, 2007 Rutgers University, New Brunswick

David Skillicorn

Title: Detecting Anomalies in Graphs

Graph data represents relationships, connections, or affinities.

Normal relationships produce repeated, and so common,

substructures in graph data. We present techniques for

discovering anomalous substructures in graphs, for example

small cliques, nodes with unusual neighborhoods, or small

unusual subgraphs, using extensions

of spectral graph techniques commonly used for clustering.

Although not all anomalous structure represents terrorist

or criminal activity, it is plausible that all terrorist or

criminal activity creates anomalous substructure in graph

data. Using our techniques, unusual regions of a graph

can be selected for deeper analysis.

David Skillicorn is a Professor in the School of Computing at

Queen's University, where he heads the Smart Information Management

Laboratory. He is also the coordinator for Research in Information

Security in Kingston (RISK). He is an adjunct Professor at the

Royal Military College of Canada. His research interests are in

data mining, particularly for counterterrorism and fraud; he has also

worked extensively in parallel and distributed computing.