Hello everyone!

Thus far, I've only talked about the theoretical side of math.  This week, I'd like to change gears and talk about applications.  In particular, let's look at how we might break up terrorist networks using graph theory.

With that out of the way, what's graph theory?  Essentially, graph theory is the study of connections.  A graph is a collection of nodes (also known as vertices or points) connected by edges (also called arcs).  Visually, we can represent a graph by drawing circles to represent the nodes, then connecting them with lines or curves, as below.  It doesn't matter if the lines cross (although there's some interesting theory behind that).  What matters is which nodes are connected.

Now that we know the basic concepts, let's start using them.  Let's pretend we're Batman, and we'd like to take out crime in Gotham.  Now, Batman has personally dealt with a lot of supervillains, so he knows exactly who they are and which ones know each other.  In a very simplified sense, we could model this with a graph, as below.  Now, villains are scary alone, but they're a lot more dangerous when they work together.  Ideally, Batman would put them all back in Arkham, but if he can only take down some of them, it makes sense to disconnect the graph as much as possible.  In general, if we can take out a given number of nodes, we want to break the graph into the smallest pieces possible.  In the example below, if we can only remove one person from the network, the best we can do is to take out Harley Quinn.But this is a bit too simple to be useful.  Let's complicate the picture a little.  Not all villains are equally dangerous.  To address this, let's add a weight to each node, that is, a score corresponding to the danger.  Then rather than breaking the graph into the smallest pieces, we would break it into pieces with the smallest total weight.  In this case, getting rid of Harley breaks the graph into three pieces, but we've still got a piece with at total threat of 20.  If we instead remove the Joker, the total threat of the remaining piece is 19, even though we don't break up the rest of the network, so the best option is to take out the Joker.  If we don't exactly know how dangerous someone is, we might use a range of weights instead.Let's add another wrinkle.  Say Batman knows who all the villains are, but he only knows some of the connections between them.  Well, we can no longer say for certain how the supervillain graph is structured, but we can still make some good guesses.  We can, for example, suppose that villains who have acquaintances in common are likely to know each other (like how Facebook figures out who you probably know).  Using similar tricks, we can make some guesses about edges that might be missing, then figure out which nodes we should remove.  If we do this with a few different randomly modified graphs, we see some nodes are removed more often than others.  We can remove the common ones to get a good answer.We also might not know all the villains.  It might make sense to assume unknown enemies are connected to large clusters of villains.  As above, we can add nodes and connect them to clusters randomly, then choose the best nodes to remove.The model we've built is still pretty simple, but it gives us a powerful tool.  We can use this sort of analysis to take down Batman villains or, more practically, disrupt terrorist networks.  Of course, the agencies fighting terrorism have different constraints (bigger data sets, less clear information, etc.) and better models to handle them.  But I hope I've at least shown you some of the analysis that might go into converting a real-world problem into a mathematical model.  Once we've done that, we can apply all the power of mathematics to solve it.

[Disclaimers: I am not an expert in this field.  The analysis here is entirely my own.  I am not associated with any government agency.  I also do not own Batman or any associated villains.  Please don't sue me.]

by