Using Networks and Graph Theory to Solve Crimes: Case Studies from Fiction and Beyond
Using Networks and Graph Theory to Solve Crimes: Case Studies from Fiction and Beyond
Man and technology have been in a constant state of evolution throughout the 20th and 21st centuries. As of today, countries have taken huge steps to protect their citizens from crimes and criminals. Indeed, Jack the Ripper would have a hard time preying on women in the streets of London with his modus operendi today. However, as law and order has evolved, so have the perpetrators. Organized crimes of the modern day are characterized by careful planning and flawless execution. Criminals often use technology to their advantage, hacking their way through cyber security systems and using proxy servers to hide their locations. As such, mathematical analysis has become an incredibly important part of fighting and tracking down organized criminals. In this post, I will discuss how mathematical analysis, specifically Network Analysis and Graph Theory have played an important part in keeping pace with criminals in the modern age.
The popular television show NUMB3RS follows a mathematician named Charlie Epps who is a professor at the fictional CalSci (California Institute of Science). He helps his brother Don Epps who leads a team of FBI investigators solve crimes with the help of mathematical analysis. In the Season 4 episode ‘Black Swan’ Charlie uses Network Analysis, specifically the Floyd-Warshall Algorithm to figure out where a suspected domestic terrorist is hiding his stash of goods. One of the members of the FBI team present a map of Los Angeles with 11 points on it which correspond to the bombers locations at different times. Charlie makes use of the Floyd-Warshall Algorithm to predict the bombers next move by finding the shortest path between points. Here’s how the algorithm works:
images and quotationfrom http://numb3rs.wolfram.com/413/
“In the four-vertex directed weighted graph illustrated above (where directed edges are indicated by arrows, edge weights by black numbers next to the corresponding arrowhead, and vertex numbers as red labels next to the corresponding vertex), applying the Floyed-Warshall algorithm gives the graph distance matrix shown at right (where the shortest distance between vertex i and j is encoded as the (i, j)th matrix element). So, for example, the shortest distance between vertex 1 and vertex 3 is 3 + 5 = 8, which is the third entry in the first row. Similarly, the shortest distance between vertices 3 and 2 is 7 + 5 + 3 = 15, which is the second entry in the third row, and so on.”
One might not think much of a drama series aired on television simply to get the attention of viewers. However, similar analysis is used by the NSA and CIA to track down terror suspects quite often. The property of Triadic Closure of Networks was something that was discussed at length in class. At face value, it is quite a simple concept: In an graph, if two nodes X and Y have a relationship with one another, and nodes Y and Z have a relationship with one another, then it is highly likely that nodes X and Z have or are likely to engage in a relationship with one another. This simple principle was used by the CIA to track down and kill Abu Musab al-Zarqawi, the leader of Al Qaeda in Iraq and the most-wanted terrorist in that war zone. Two of the three key nodes in this process were Abu Musab al-Zarqawi himself and Sheik Abdul Rahman, described as his “spiritual advisor”. The relationship between these two individuals was used, along with that of a CIA informant to create a network which worked on the principle of triadic closure. This network was then analyzed for weeks before the relationship was deemed strong enough to go through with the final stage of the operation: killing Musab al-Zarqawi. Though the exact details of the operation still remain classified, there remains no doubt that members of the CIA have taken courses similar to INFO 2040 while they were in college.
Sources:
2. http://numb3rs.wolfram.com/413/
3. http://www.tvguide.com/tvshows/numb3rs-2008/episode-13-season-4/black-swan/191696
For further reading on the Floyd – Warshall Algorithm (I didn’t include this analysis for lack of space)
4. http://www.math.cornell.edu/~numb3rs/lipa/black_swan.html