Decycling Graphs and Terrorists
In 2009 I was working at MIT coordinating math research for Research Science Institute for high school students. One of our students Jacob Hurwitz got a project on decycling graphs.
“Decycling” means removing vertices of a graph, so that the resulting graph doesn’t have cycles. The decycling number of a graph is the smallest number of vertices you need to remove.
Decycling is equivalent to finding induced forests in a graph. The set of vertices of the largest induced forest is a complement to the smallest set of vertices you need to remove for decycling.
Among other things, Jacob found induced trees and forests of the highest densities on graphs of all semi-regular tessellations. On the pictures he provided for this essay, you can see an example of a tessellation, a corresponding densest forest, and a corresponding densest tree. The density of the forest and the tree is 2/3, meaning that 1/3 of the vertices are removed.
To motivate RSI students I tried to come up with practical uses for their projects. When I was talking to Jacob about decycling, the only thing I could think of was terrorists. When terrorists create their cells, they need to limit connections among themselves, in order to limit the damage to everyone else in the cell if one of them gets busted.
That means the graph of connections of a terrorist cell is a tree. Suppose there is a group of people that we suspect, and we know the graph of their contacts, then the decycling number of the graph is the number of people that are guaranteed to be innocent.
Have you noticed how Facebook and LinkedIn are reasonably good at suggesting people you might know? The algorithm they use to analyze the data is fairly effective in revealing potential connections. Recently, someone was able to download all of the Facebook data, which means that any government agency ought to be able to do the same thing. They could analyze such data to discover implicit connections. As a byproduct of looking for terrorists, they would also discover all of our grudges.
Oh dear. What are they going to think when they find out I’m not connected to my exes?
Share:
Marat:
Good post, thank You. I’ll translate it and put it here:
20 September 2010, 1:30 amhttps://ursa-tm.ru/forum/index.php?/topic/5432-%d0%b0%d0%bd%d0%b3%d0%bb%d0%be%d1%8f%d0%b7%d1%8b%d1%87%d0%bd%d1%8b%d0%b5-%d0%b1%d0%bb%d0%be%d0%b3%d0%b8-%d0%be-%d1%80%d0%be%d1%81%d1%81%d0%b8%d0%b8-%d0%b8-%d0%be%d0%ba%d0%be%d0%bb%d0%be/
Best regards,
Quick Links | A Blog Around The Clock:
[…] Decycling Graphs and Terrorists […]
23 September 2010, 10:47 amAlex:
This reminds me the kind of problems Jon Kleinberg works on https://bit.ly/bZglbZ. One of his talks on these: https://bit.ly/bom7ZG
23 September 2010, 12:01 pmmisha:
Propagation of gossip is another example where cycles may be unpleasant.
24 September 2010, 2:25 amSAT Math Prep:
Very interesting article! I studied engineering in graduate school and took some advanced math courses, but decycling is something I’ve never heard before. I’ll be bookmarking this blog and coming back often!
24 September 2010, 7:54 pmSasha Gutfraind:
Tanya,
Your point about sparsifying the terrorist networks is well-motivated. There is research that suggest this. However, there are further points that need to be considered. (1) not all trees are the same, c.f. a binary tree vs. a star. The latter has very large number of people a short distance away, (2) terrorists might be willing to sacrifice “resilience” of their network in order to make it easier for the network to function. For example, if the average distance in your network scales as Theta(n), it’s hard to be a successful terrorist.
2 October 2010, 7:08 pm