http://www.npr.org/2010/12/03/131755378/u-s-connects-the-dots-to-catch-roads... U.S. 'Connects The Dots' To Catch Roadside Bombers by TOM GJELTEN EnlargeDavid Gilkey/NPR Marines on patrol in Afghanistan's Helmand province walk near a blast crater from a homemade explosive device. Roadside bombs are the leading killer of U.S. troops in Iraq and Afghanistan. The American military has turned to mathematics and social network analysis to help identify bombers and their supporters. December 3, 2010 With his doctorate from Princeton, Army Gen. David Petraeus, the U.S. commander in Afghanistan, has become the prime example of a special breed of soldier: the warrior-scholar, trained in history and politics as well as how to fight wars. Now there's a variation on the theme: the warrior mathematician, adept in the complex modeling that has become a key part of military planning. The Problem: Assessing The Enemy Soldiers who will be involved in the effort to prevent roadside bombs, known as improvised explosive devices, or IEDs, are presented with the following scenario. You are an infantry patrol leader and your unit encounters the following chain of events: Raheim, a known enemy operative, was found carrying a cell phone which he has used to maintain constant contact with two individuals, Jalil Al Tikrit and Farrah Imir. Text messages on Raheim's phone reveal a plot by Jalil Al Tikrit and another unknown individual to place an IED in a culvert along a supply route commonly used by U.S. forces. Raheim is immediately taken into custody and handed over to local authorities. Hours later, a local shopkeeper named Ibraheem is seen talking to a man named Habib Muhammed, but Ibraheem was not seen with anyone else. Later, an unidentified individual and Habib Muhammed are captured in a culvert. Habib Muhammed was found to be carrying a credit card owned by Farrah Imir along with a list of supplies in Farrah Imir's handwriting that seems to be a manifest for building and placing an IED. As you ponder the events of the day, it dawns on you that the unknown individuals are not unknown at all. You know their identities. The task: Build a model of the network of individuals and use it as part of your analysis to develop a target. To see the answer, scroll down the page. Course Guide, Advanced Network Analysis and Targeting: A Social Networks Approach to Targeting, by Ian McCulloh, Anthony Johnson, and Helen Armstrong. Used by permission. With roadside bombs the leading killer of U.S. troops in Iraq and Afghanistan, military commanders have turned increasingly to the use of social network analysis to identify the key players in the groups responsible for the bombs, which the military calls improvised explosive devices, or IEDs. The approach is rooted in the belief that a roadside bomb is never the work of one individual alone. 'Attack The Network' "Someone has to build it, someone has to place it, someone has to do surveillance on the place where you place it," said Kathleen Carley, a professor of computer science at Carnegie Mellon University and the unofficial godmother of social network analysis as applied to the IED problem. "If you're trying to defeat IEDs, what you're talking about is understanding that whole process b who is involved, how they are connected to each other b so that you can figure out where the best place is to intervene," Carley said. The idea is that an analysis of the social network behind roadside bombing attempts will make it possible to identify which members of the group are most vital to the operation and most important to stop, in order to disrupt the entire network. "Any organization has relationships," said Army Maj. Ian McCulloh, deputy director of the Counter-IED Operations Integration Center in Baghdad and one of Carley's former students. "Civilian firms have used social network analysis for decades to map out those relationships and identify the organization's vulnerabilities. The same principles apply to threat networks. This helps us identify their vulnerabilities," he said. The U.S. military's biggest success so far in the use of network analysis was the capture of Saddam Hussein in December 2003. He was found after soldiers diagrammed the social networks of his chauffeurs and others close to him. The technique is now used extensively to identify the key figures in insurgent groups in both Iraq and Afghanistan. "Attack the Network" is the motto of the anti-IED effort. Much is at stake. Of 3,486 U.S. service members killed in Iraq since 2003 by hostile action, 2,196 have died as a result of IED explosions, according to figures released by the Pentagon and other sources. In Afghanistan, nearly 90 percent of U.S. military deaths due to hostile action b 1,075 as of Dec. 2 b have been caused by IEDs. Connecting The Dots McCulloh, who received his doctorate in network science from Carnegie Mellon, is an expert in the application of relational algebra to the study of IED networks. He teaches other soldiers in the analytical techniques. While on leave last month from his post in Baghdad, McCulloh taught a one-week class in "Advanced Network Analysis and Targeting" to a group of Iraq-bound soldiers at Fort Bragg in North Carolina. Each of the soldiers was to be involved with the anti-IED effort in Iraq, primarily in the selection of targets for military operations. Answer: The Network In the exercise above and the solution below, each individual is a "node," displayed as a dot linked by lines to other dots. Some nodes are more important than others, depending on their "betweenness" scores, determined, basically, by how well connected an individual is to others in the network. When a "highly central node" emerges, that is a person the military may try to capture or kill. Courtesy of Kathleen Carley In this case, Habib Muhammed, who is connected to three others in the network, is the "most central" node. One of the goals listed in McCulloh's course guide is to help soldiers "mathematically quantify influential network nodes ... in order to provide warfighters with objective measures for the relative values of various potential targets." For many of the soldiers in the course, the mathematics instruction was daunting. "I took some math in high school, but mainly it was statistics," said Chief Warrant Officer John Fleshman, an 18-year Army veteran. "Fortunately, Major McCulloh breaks it down to high school level." Fleshman, an artillery targeting officer, said the mathematics he learned in his Fort Bragg class made it easier to identify the most important targets for anti-IED and other counterinsurgency operations. "You have to know where to look, and this helps you know where to look," he said. In McCulloh's class, "connecting the dots" is taken literally. He shows his students how to visualize a network of all of the people involved in an IED cell. On a computer screen, each individual is a "node," displayed as a dot linked by lines to other dots. Some nodes are more important than others, depending on their "betweenness" scores, determined, basically, by how well connected an individual is to others in the network. "From these guys and these guys, it's a lot shorter to go through D than it is to go through E and F," McCulloh points out to one of his soldier students. "So that's what gives D high betweenness centrality. He also has an average shorter distance to everybody, so in many ways, D is the highly central node." When the U.S. military is looking for key people to capture or kill, you do not want to be identified as "a highly central node." Same Conclusions, But Faster Military commanders and intelligence analysts have long understood the need to study relationships among individuals on the enemy side. What's new is how sophisticated and mathematical the process has become. McCulloh, a brainy young officer who also teaches at West Point, thinks the Army needs more warrior-mathematicians like himself. Still, the lanky redhead had to learn some humility when he went to work a couple of years ago in Afghanistan alongside grizzled intelligence veterans. "I thought I was going to go in there with my network analysis and my academic background, and I was going to find all of the hidden nodes, the key guys," McCulloh says. "I was going to find bin Laden and all the guys that were leading the terrorism. And I was actually a little disappointed to find that everybody I found in any of the data sets that I looked at, we already knew about." EnlargeTom Gjelten/NPR Chief Warrant Officer Michael Kanabrocki (left) attends a class led by Maj. Ian McCulloh at Fort Bragg, N.C., on using mathematical modeling and social network analysis to identify key players in groups responsible for roadside bombs in Iraq and Afghanistan. The veterans had used hunches and intuition to figure out the networks. But McCulloh says his math and computer science training did help him work more quickly than the old-timers could. "The first network I looked at probably had about 200 to 300 nodes in it," he says. "It took an analyst with 26 years of experience about five days to look through it and identify where they felt the key vulnerabilities were. I was able to put it into the software that I use and do some basic network analysis and in about 15 to 20 minutes I had the same conclusion." Advantages To Mathematical Precision As with any computer operation, the quality of the analysis depends on the quality of the data going in. Carley, the Carnegie Mellon University professor who has been working with the military since she got out of college, says if soldiers are to understand a roadside bombing network, they need information b from people they capture, from informants and from intercepted phone calls. "You try to find things about who else they know," Carley says, "who they're related to, where they've been in the past, where were they trained, what other kind of groups did they belong to, things like that." In this regard, Carley says, network analysis presents yet another advantage. A computer-generated network diagram can help soldiers "see" what data they are missing and still need to gather. The mathematical precision that comes with this analysis also gives soldiers more confidence in their judgments than might be the case with hunches and intuition. That's important to military lawyers who have to approve an operation to capture or kill someone. Maj. Eugene Vindman, a JAG officer, or judge advocate general, says McCulloh's network analysis course put him and other military lawyers in a better position to carry out oversight responsibilities in Iraq. "[You could] maybe do a little bit of analysis on your own or ask some intelligent questions of the targeteers," Vindman says, "to make sure that the target they've identified is not a guy that might have made a wrong phone call to a bad guy but actually has enough links to that bad guy through other activities to actually be a bad guy and therefore be a legal military target."