© Springer-Verlag Berlin Heidelberg 2006 Detecting Anomalies in Cargo Using Graph Properties

The ability to mine relational data has become important in several domains (e.g., counter-terrorism), and a graph-based representation of this data has proven useful in detecting various relational, structural patterns [1]. Here, we analyze the use of graph properties as a method for uncovering anomalies in data represented as a graph. Graph Properties. While our initial research examined many of the basic graph properties, only a few of them proved to be insightful as to the structure of a graph for anomaly detection purposes. For the average shortest path length L, we used the Floyd-Warshall all-pairs algorithm. For a measurement of density, we chose to use a definition that is commonly used when defining social networks [4]. For connectedness, we used a definition that Broder et al. [2] defined in their paper. For some of the more complex graph properties, we investigated two measurements. First, there is the maximum eigenvalue of a graph [5]. Another, which was used in identifying e-mail “spammers”, is the graph clustering coefficient [3]. Synthetic Results. For each of our tests, we created 6 different graph size type