Research and Advances
Computing Applications Contributed articles

Reshaping Terrorist Networks

To destabilize terrorist organizations, the STONE algorithms identify a set of operatives whose removal would maximally reduce lethality.
Posted
Nelly Avila Moreno escorted by soldiers
  1. Introduction
  2. Key Insights
  3. Related Work
  4. Terrorist Organizational Networks
  5. Terrorist Successor Problem
  6. Multiple Terrorist Successor Problem
  7. Lethality Functions
  8. Which Vertices to Remove?
  9. Implementation and Experiments
  10. Conclusion
  11. Acknowledgment
  12. References
  13. Authors
  14. Footnotes
  15. Figures
Nelly Avila Moreno escorted by soldiers
Nelly Avila Moreno, a former high-ranking member of Colombia's Marxist FARC guerrillas, is escorted by soldiers on August 10, 2009, as she arrives at a press conference in Medellin, Colombia, to report on her peace efforts since her Surrender.

In 2008, a Revolutionary Armed Forces of Colombia, or FARC, commander named Nelly Avila Moreno (a.k.a. Karina) turned herself in to Colombian authorities in response to the announcement of a $1 million award for her arrest. Unlike expensive and risky operations to capture terrorists (such as Al Qaeda’s Khalid Sheikh Mohammed and the Kurdish PKK’s Abdullah Ocalan), Karina had been captured at minimal expense in terms of both financial cost and lives put at risk. The Shaping Terrorist Organization Network Efficiency, or STONE, software platform we developed is designed to identify a set of key operatives in a terrorist network whose removal would maximally defang the organization through a variety of reward programs and capture operations. STONE answers who should be the targets of the reward program and if a government wishes to destabilize a terrorist network and have funds to remove k people, which k people it should target.

Back to Top

Key Insights

  • Identifying terrorists whose removal would maximally destabilize their networks saves civilian and military lives, as well as financial costs.
  • Measuring lethality of terrorist networks, STONE algorithms help predict who will succeed a removed terrorist leader with more than 80% accuracy.
  • STONE was tested extensively on data four real terror groups: Al-Qæda, Hamas, Hezbollah, and Lashkar-e-Taiba.

Such removal operations are essential to international security. Though world governments spent more than $70 billion fighting terrorism from 2001 to 2008, reducing the number of transnational attacks by 34%, there was a net increase in terrorism fatalities by 67 deaths per year during the same period.11 Counterterror efforts have weighed strategic actions that try to address the root causes of terrorism by providing incentives to all parties to reach agreement, with many conducting strategic studies to reduce terrorism.19 However, strategic defeat of terrorist organizations is rare, despite some notable successes (such as the Provisional IRA in Ireland and Aum Shinrikyo in Japan).4 As a consequence, tactical actions aimed at destabilizing terror networks are still necessary today.

STONE uses three novel algorithms:

Terrorist Successor Problem (TSP). When a terrorist r is removed, it identifies the probability that r is replaced by another terrorist v;

Multiple Terrorist Successor Problem (MTSP). When multiple terrorists are removed from a network, it identifies the new possible networks that might arise, together with an associated probability distribution; and

Terrorist Network Reshaping Problem (TNRP). It uses the results generated by MTSP to identify a set of k terrorists to remove from the network so as to minimize the expected efficacy of the resulting network.

In the terrorist networks we consider, each vertex (such as Abdullah Azzam) could have many properties, including a status property specifying if he is alive, dead, or jailed; a role property specifying whether he is a fundraiser, ideologue, or recruiter. Figure 1 outlines a toy network where, in addition to the vertex properties, we also consider hostility of a vertex toward the West, capability to launch attacks, and blowback if captured. A property labeling ρ(v, p) tells us the value of property p for vertex v. We explain other properties of terrorists in greater detail later. However, STONE can work with any set of properties, not just these. Each vertex in the network also has a rank—coded from 1 to 10, with 10 being the highest; multiple people may have the same rank.

We developed the STONE algorithms and tested them with the help of military, policy, and terrorism experts known to us, all of which (with one exception) having written books related to counterterrorism and carried out detailed analyses of specific terrorist groups; the exception was a retired U.S. Army general with considerable expertise fighting terrorists and insurgents. Our tests included both synthetic graphs and real-world open source terrorist-network data. Our experts gave us data on Hamas,12 Hezbollah,12 Lashkar-e-Taiba,6,19,20 and Al-Qaeda, including affiliates like Al-Qaeda in the Islamic Maghreb and Al-Qaeda in the Arabic Peninsula.5 The data included properties of the terrorists and links between them. Our experts also told us which terrorists were removed from a network, when they were removed, and who replaced them.

We tested the accuracy of our solution to TSP as follows: We identified the most probable successor v when a terrorist r is removed, together with his/her probability pmax of succeeding r, as well as all terrorists whose probability of succeeding r was “close enough” (within 2%, 3%, 4%, or 5% of pmax). We did not perform the test with MTSP for two reasons: It is an intermediate step to solving TNRP, and we did not have data as to when multiple terrorists were removed in close temporal proximity. We used our solution to MTSP and various lethality functions to solve TNRP by identifying a set of k terrorists in the network (varying k from 1 to 10). As we were not able to conduct experiments involving the real removal of terrorists, we presented the results to our experts and asked them to score the effectiveness of our suggestions on a scale of 1 to 5, with 5 the highest. STONE did well. The algorithms we describe here can also be used to reason about drug, criminal, and money-laundering networks.

Back to Top

Related Work

Identifying key actors in networks is studied through centrality measures; for example, Memon13 used traditional centrality measures to identify key actors, and Memon and Larson14 defined efficiency of a network using prior work of Latora and Marchiori.9 Memon and Larsren14 proposed a position role index to distinguish between gatekeepers and followers in such networks and define “dependence centrality,” or DC. Memon and Larsen14 showed the values of DC on Krebs’s 9/11 network.7 Carley3 proposed the CONSTRUCT-O model to measure destabilization of a network through the ability to diffuse information throughout a network, the ability to reach consensus, and the network’s ability to perform tasks. Carley2 suggested “isolation” strategies yielding valuable “objective functions” can be used within the lethality measures described here. Ozgul17 studied the problem of detecting cells in terror networks, proposing such algorithms as GDM and OGDM. Lindelauf10 studied the tension between the need to communicate and the need to stay covert in a terror network via a game-theoretic model.

In contrast, STONE develops a mathematical model of who replaces a “removed” individual in a terrorist network, taking into account both network structure and vertex properties, as well as the need for the terrorist network to achieve operational effectiveness. STONE follows the first approach to identifying how a network will evolve when a set of vertices is removed, using the information to decide which set of nodes to remove; it is not wise to remove vertices from networks without first understanding the effects of the removals.

Back to Top

Terrorist Organizational Networks

A terrorist organization network (ON) is an undirected graph with vertices and edges. Each vertex is labeled with some properties drawn from a set VP of properties, as described earlier and shown in Figure 1.

We first define what happens when we replace a vertex r (the vertex being removed) in ON with a vertex v; we do not suggest v replace r, just define what happens. Suppose an analyst replaces vertex B in Figure 1 with vertex A. STONE assumes A retains all his connections and inherits B‘s connections. An interesting question concerns what happens to A‘s properties. In STONE, a function set by an analyst specifies what properties are inherited from the removed vertex and what properties are not. In our examples, the role and rank properties are inherited while all other properties stay the same. Figure 2 shows that A‘s properties are identical to his prior properties, except for his promotion from his old rank of 8 to B‘s rank of 9.

Back to Top

Terrorist Successor Problem

TSP addresses what happens when vertex r is removed from the terrorist network ON who replaces r. STONE solves TSP in three steps:

Vertex properties. In addition to the properties discussed earlier, we define specific network-centric properties: Weighted Removal PageRank (WRP) measures the influence of a vertex, and Property Oriented Clustering Coefficient (POCC) measures how tightly connected a vertex is to neighboring vertices;

Candidate replacements. We formally define the set of candidates that can replace a vertex. STONE allows counterterrorism analysts to specify properties v must satisfy to replace removed vertex r; for instance, it might be the case that v must be able to play the same role as r. In Figure 1 and Figure 2, this means D cannot replace B if D‘s role was fundraising instead of operations; and

Candidate probabilities. Identifying candidates, we must assign a probability that a given candidate replaces the vertex r being removed.

Network properties of vertices. Here, we describe two special vertex properties—WRP and POCC—used by STONE by leveraging Google’s PageRank and clustering coefficients in social networks. STONE allows many other classical centrality measures (such as degree centrality and between-ness centrality), though they are not covered here. We chose WRP and POCC, as they measure the influence of a vertex and the strength of connection of a vertex, respectively. Our hypothesis is that influence and connectedness play a role in determining who is most likely to be elevated to succeed a removed terrorist.

WRP. WRP scores the influence of a vertex by looking at the influence of the associates and family members surrounding him—his immediate neighbors in the network. A person with influential connections is expected to be influential; for instance, in the network associated with Al-Qaeda, Khalid Sheikh Mohammed (KSM) was highly influential, as his immediate connections included top Al-Qaeda leaders Osama Bin Laden, Ayman al-Zawahiri, and others. When he was captured (removed), the WRP calculation for a vertex with respect to KSM would measure the relative influence of the vertex. KSM was replaced by Abu Faraj al-Libbi who had a high influence score, as measured by WRP. WRP extends PageRank1 to handle three social factors:

Vertices. Vertices in ON have a rank that must be taken into account when computing the importance of a vertex;

Importance of a vertex. WRP(v, r) denotes the importance of a vertex v in ON, taking into account the fact a vertex r is being considered for removal; and

Undirected graphs. Terrorist organization networks are undirected graphs, not directed graphs like the Web.

The WRP of v is a dynamic quantity that depends on removal of node r. The higher a vertex’s WRP with respect to a vertex r being considered for removal, the more likely v is to be a replacement vertex for r, assuming certain other conditions described later. WRP is formally defined in Figure 3. The first term of the formula describes the influence of vertex v with respect to all vertices in the network, except for r, and multiplies it by (1 – δ) to capture the probability rank plays a role in the vertex’s importance. The second term looks at the importance of v‘s connections, saying each of v‘s neighbors (u) distributes its importance equally among its neighbors, excluding the vertex r being removed. By multiplying the summation of the second term by δ, STONE is saying the probability that network effects are important is δ. Figure 4 outlines the WRP of the vertices in the small terrorist network of Figure 1, assuming B is being removed.

Property-oriented clustering coefficient. In network theory, clustering coefficients21 capture how “tightly” a vertex is connected to other vertices in a network. Intuitively, the more tightly connected a terrorist is to other terrorists in his network, the more likely he is to gain their support and be promoted; for instance, when KSM’s was captured by U.S. forces in Rawalpindi, Pakistan, in 2003, his successor needed to be tightly connected to his peers to be promoted up to KSM’s position in the network, as was indeed the case with Abu Faraj al-Libbi, who succeeded KSM.

The clustering coefficient of vertex v is technically the percentage of pairs of v‘s neighbors connected to one another. In STONE, we introduce property-oriented clustering coefficients and do not just look at immediate neighbors. The k-neighborhood of a vertex v consists of all vertices at distance k or less from v. From those vertices in v‘s k-neighborhood, we are interested only in vertices satisfying a set P of properties specified by an analyst because we use property-oriented clustering coefficients to identify who might replace a vertex r being removed. As a consequence, we restrict interest to only vertices with certain properties, as only vertices with them might be able to influence selection of the replacement vertex; for instance, selection of the operations chief of Lashkar-e-Taiba—if the current operations chief Zakiur-Rehman Lahkhvi is removed—might be determined only by the current chief of Lashkar-e-Taiba, certain top members of the operations section of Lashkar-e-Taiba, members of Lashkar-e-Taiba’s Council of Elders, or Majlis-e-Shura. Others directly linked to Zaki-ur-Rehman Lakhvi and in his k-neighborhood may not formally influence selection of his successor.a While WRP reflects the influence of a single terrorist, POCC thus captures how tightly integrated that terrorist is with his peers in the organization; POCC is defined in Figure 5.b

Candidate replacements. STONE assumes the analyst specifies weights for each vertex property defining the relative importance of each property; for instance, the weight of a vertex’s hostility might be set at 0.4, while the weight of a vertex’s POCC might be set at 0.2, indicating the analyst’s assessment of the situation for the group that the POCC is only half as important as the vertex’s hostility.

Let αi be a weight associated with each property pi in our suite of properties such that the α‘s add up to 1.c Each vertex v that may replace a removed vertex r has a replacement value rv(v, r), defined as follows

ueq01.gif

STONE allows an analyst to specify any set C of properties a vertex should have in order to be an appropriate replacement node for a vertex r that is being removed; for instance, the analyst may specify vertex v must be either a member of the terror network’s leadership council or a member of the same department (such as operations) to which the vertex r being removed belongs. STONE supports many network-centered properties not discussed here (such as degree centrality, between-ness centrality, and closeness centrality). We now define when a vertex v is considered a candidate replacement for a vertex r.

When is v a candidate to replace r? When v satisfies condition C, rank(v) ≤ rank(r), and there is no other vertex u (different from both v and r) such that u satisfies the previous two conditions and such that u‘s replacement value is strictly greater than v‘s.

Example 1. Consider the network in Figure 1 where B is to be removed, and suppose C says the distance between B and v must be 1. Moreover, suppose rv(v, B) is computed, taking into account the WRP (with α0 = 0.2), POCC with k = 2, and P = Ø (with α1 = 0.2), the node rank (with α2 = 0.4), and node capacity (α3 = 0.2).c The possible candidates to replace vertex r = B are then:

ueq02.gif

Here, A is the best candidate, with E a close second.

Probability of a candidate. We now define the probability of a candidate, or the probability v will replace r:

ueq03.gif

The probability that v replaces removed node r is the ratio of v‘s replacement value divided by the sum of the replacement values of all candidates to replace v; for instance, the probabilities that vertices C, A, D, E, F from Figure 1 (Example 1) replace B are listed in Figure 6. Observe that P(C, B) = 0 because C‘s rank is greater than B‘s rank, and P(F, B) = 0 because the distance between B and F is greater than 1.

Back to Top

Multiple Terrorist Successor Problem

Instead of removing a single vertex r, what if an analyst wants to remove a set R of vertices? For example, in June 2012, India captured two Lashkar-e-Taiba terrorists in quick succession: Abu Jundal, who was present in the control room in Pakistan directing the November 2008 Mumbai attacks, was reportedly captured in a coordinated operation by India, Saudi Arabia, and the U.S., and Tunda, a top Lashkar-e-Taiba bomb maker, was captured in August 2013 along the India-Nepal border. Most security agencies aim to capture multiple terrorists simultaneously. In such cases, many networks are possible (such as if n people could replace Abu Jundal and m people could replace Tunda, then there are mn possible new networks). MTSP is designed to help determine probabilities for the new networks.

Now suppose, as in the single vertex removal case, an analyst has specified a condition C replacement vertices must satisfy. A candidate replacement set XR for a set R of vertices being removed with respect to condition C is a set of pairs (r, cr) (r being a removed vertex and cr being its replacement) satisfying four conditions:

  1. Every removed vertex has a replacement. For each rR, there is a pair (r, cr) ∈ XR and
  2. Replacement vertices cannot be removed. {cr | (r, cr) ∈ XR} ⊆ (V – R) and
  3. Replacement nodes must be candidates. For each pair (r, cr) ∈ XR, cr is a candidate to replace r with respect to condition C and
  4. Candidates can replace only one vertex. There are no two r, r′R such that (r, cr), (r′, cr) are both in XR.

The following example returns to our running example to show what happens if an analyst removes the set {B, C} of vertices from Figure 1 and Example 1.

Example 2. Suppose an analyst wishes to remove the set R = {B, C}. The set of candidate replacements of B is {A, D, E}, and the set of candidate replacements for C is {A, B}. A cannot replace both node B and C, and B is not a valid candidate to replace C because B is to be removed. The replacement sets for R are X′R = {(B, D), (C, A)}, and X″R = {(B, E), (C, A)}.

There may be many different candidate replacement sets XR with respect to R and C. The probability P(XR) that XR will in fact be the replacement for R is simply the product of the individual probabilities cacm5708_a.gif (cr, r) that cr will be the replacement for the vertex r. To see how this works, return to the toy example of Figure 1 and Example 2.

Example 3. We have cacm5708_a.gif (B, C) = 0 and cacm5708_a.gif (A, C) = 1, and cacm5708_a.gif (D, B) = 0.31 and cacm5708_a.gif (E, B) = 0.34. So the probability of the replacement set X′R = {D, A} is equal to (0.31·1) / (0.31+0.34) = 0.46, and the probability of the replacement set X″R = {E, A} is equal to (0.34·1) / (0.31+0.34) = 0.54.

When a given set R of vertices is to be removed, let Xmax be the candidate replacement set with the greatest probability. As there is much uncertainty in the parameter settings (such as choice of weights for each property, the choice of k in the definition of property-oriented clustering coefficients and the choice of condition C the counterterrorism analyst sets), the STONE algorithms do not want to just return Xmax to the analyst. Rather, STONE returns all candidate replacement sets XR whose probability is at most δ percentage points smaller than Xmax‘s probability (see Figure 7). Note Xmax is not an input to this problem; STONE algorithms solve it automatically without having Xmax as an input. STONE developers prove MTSP can be solved in polynomial time by leveraging an efficient algorithm due to Murty16 that enumerates, in increasing order of cost, all solutions to the minimal matching in a complete, weighted, bipartite graph, as in Figure 7. Leveraging Murty,16 STONE algorithms enumerate, in decreasing order of probability, all solutions to the maximal matching, until STONE reaches a solution XR such that cacm5708_a.gif (Xmax) – cacm5708_a.gif (XR) > δ.

Back to Top

Lethality Functions

When an analyst recommends a set of nodes to be removed from a network (such as in a capture operation), the analyst must consider the possible new networks that might result, as well as their lethality. We have covered the former and now turn to ways to measure network lethality, including four such methods: L1 assesses the difference of ranks of violent-prone and violence-adverse node; L2 modulates L1 by degree of the vertices involved; L3 modulates L1 by using WRP instead of degree; and L4 uses regression to correlate L1, L2, and L3 with associated attacks.

A vertex is violence-prone if both its capability and its hostility exceed analyst-defined thresholds; otherwise, the vertex is violence-averse. STONE uses VPR(ON) and VA(ON) to denote the set of all violence-prone and violence-averse vertices, respectively, in ON; Figure 8 includes three lethality functions.

L1 says the lethality of a network is the sum of the ranks of violence-prone vertices minus the sum of the weights of the violence-averse vertices; that is, think of the violence-prone individuals’ violence being moderated by those who are violence-averse; for instance, in the 1990s and early 2000s, the terrorist group Students Islamic Movement of India had a violence-prone wing (that later broke off and became the Indian Mujahideen) and a violence-averse wing (that continues to today).

Example 4. Consider the network ON in Figure 1 and suppose vertices A, B and D are violence-prone, while C, E, and F are violence-adverse. Then, L1(ON) = wt(A) + wt(B) + wt(D) – wt(C) – wt(E) – wt(F) = 1.

L2 says the lethality of a vertex is the degree of the vertex times the rank of the vertex and the lethality of a network is the sum of the lethality scores of violence-prone vertices minus the sum of the lethality scores of violence-averse vertices. The third lethality function is similar but uses WRP instead of degree.

Example 5. Continuing Example 4, an analyst has L2(ON) = 48, while L3(ON) = 2.69.

Though many other lethality functions are possible, we do not cover them here, with the exception of a hybrid lethality function:

Hybrid lethality function. A suggestion made independently by a reviewer and by terrorism expert Daveed Gartenstein-Ross of the Foundation for Defense of Democracies, a Washington, D.C.-based think tank, is to define lethality based on attack data. We thus aimed to correlate network structure with attack data. As outlined in Figure 9, the network associated with a particular group was initially ON0 for some period I1 of time at which time terrorist r1 was removed, leading to network ON1. After time period I2, a terrorist r2 was removed, leading to network ON2. During each period Ij, the group launched some number Aj of attacks. The variables Aj are measures of the lethality of the network Nj–1. For each group, we were thus able to build a table. The jth row of this table corresponded to the time period Ij and the columns contained the values of L1(ONj), L2(ONj), L3(ONj) as independent variables and Aj as a dependent variable. Using standard multivariate regression analysis,15 we learned a hybrid lethality function Lh relating the values returned by L1, L2, L3 with each of these lethality variables. STONE developers call this hybrid function h. We conducted experiments to check the effectiveness of the hybrid lethality function in predicting the number of attacks. We ran the tests with our Lashkar-e-Taiba network dataset (1990–2012) and Al Qaeda dataset (2001–2013). In the case of our Lashkar-e-Taiba dataset, STONE found that our learned hybrid lethality function Lh could help us predict the number of attacks by Lashkar-e-Taiba. The Pearson correlation coefficient between the true number of attacks and the predicted number of attacks by Lashkar-e-Taiba on blinded data was 0.83. However, when we learned Lh from the smaller Al-Qaeda dataset, the Pearson correlation coefficient between the actual number of Al Qaeda attacks and our predictions was 0.652. Lh thus provides an accurate method of predicting number of attacks by a terror network, with accuracy increasing along with the amount of data an analyst happens to have.

Back to Top

Which Vertices to Remove?

In order to decide which k vertices from a network (possibly excluding some set EX of vertices) to remove, STONE would first define possible terror networks (PTNs) and substitution diagrams (graphs). Figure 10a outlines a sample substitution diagram. Suppose R is a set of vertices being considered for removal; R is the root of the substitution diagram. We know several candidates might be in line to replace the vertices in R. Call these candidates C1, …, Cn using the definition given earlier. Each Ci is a child of R with the probability pi labeling the link, where pi is the probability that Ci replaces R. If Ci were to replace R, STONE would need to find a replacement for the set Ci of vertices. Figure 10a outlines this relationship through an example where C1 has two possible candidate replacements—D1 and D2. Likewise, C2, which is a candidate set to replace R, has only one candidate to replace it—D2; see Figure 10b for the substitution diagram for the running example.

A possible replacement chain (PRC) is a path from the root R of the substitution diagram to any leaf. The labels of the nodes along such a path represent the sequence of removals and replacements in the PRC; for instance, the path R, C2, D2 represents the removal of R from the network, its replacement by C2, and replacement of C2 by D2. Every PRC X1, …, Xm generates a PTN as follows: Starting with the terrorist network ON, let ON1 be the network obtained by replacing R with X1 in network ON. Similarly, let ON2 be the result of replacing X1 in network ON1 by X2. STONE does this repeatedly until Xm–1 in ONm–1 is replaced with Xm. The resulting network is a possible terrorist network.


STONE addresses the problem of identifying a set of k terrorists in a terrorist organization network whose capture and removal would minimize the expected lethality of the resulting network.


Our running example includes two PTNs—N1 and N2 (see Figure 11). The probability of a PTN with respect to a path is the product of the probabilities labeling the edges. The probability cacm5708_a.gif (N2) of the PTN N2 is 0.54 · 1 = 0.54.

A leaf node in the substitution diagram can be reached via multiple paths, as the same PTN may be generated by multiple PRCs. The probability of the PTN is the sum of the probabilities of the PTN with respect to each replacement chain that allows STONE to reach the leaf node. Reaching the leaf node is the case with the PTNs corresponding to the leaf D2 in Figure 10a.

Suppose R is a set of vertices to be removed, PTN(ON, R) is the set of all PTNs that could result, and L is a lethality function. The statistical expected lethality of the network when R is removed is defined by STONE as

ueq04.gif

Returning to our running example, the lethality L2 of the possible network N1 is L2(N1) = 17 while L2(N2) is 2. The expected lethality is then LEV(ON,R) = ΣN∈PTN(ON,R) cacm5708_a.gif (N) · L2(N) = (0.46 · 17) + (0.54 · 2) = 8.9.

TNRP.

Input. A terrorist organizational network ON, a condition C that each terrorist being removed must satisfy, and a number k.

Output. Set R of vertices such that

  1. |R| ≤ k and
  2. Each rR satisfies condition C and
  3. There is no set R′ of vertices satisfying (i) and (ii) such that LEV (ON, R′) < LEV(ON,R).

An analyst may specify conditions C that removed terrorists must satisfy; at the very least, the vertex must be alive or other. We can also imagine an analyst saying certain terrorists should not be removed due to potential political fallout; for instance, even though the U.S. Department of State announced a $10 million reward in 2012 for information leading to the prosecution of Lashkar-e-Taiba leader Hafez Saeed, he continues to move freely within Pakistan, giving press conferences and speaking at public rallies.

As solving the TNRP is likely NP-hard, STONE developers developed a greedy algorithm to solve it as follows: Algorithm 1 (see Figure 12) starts with R = Ø. In each iteration, it finds the removable vertex r, which maximally reduces expected lethality (line 8 of the algorithm in Figure 12). Line 10 checks if adding r to R reduces expected lethality. If so, r is added to R (line 11) and the STONE algorithm repeats until either R has k elements or adding more elements to r does not reduce the expected lethality.

In our running example with lethality function L3 and k = 2, Algorithm 1 suggests removing D and F, decreasing the expected network lethality to –8.87.

Back to Top

Implementation and Experiments

We implemented all algorithms in this article in 1,500 lines of Java, running them on an AMD Opteron Quad-Core 2354 at 2.2GHz, 8GB RAM machine under the Linux operating system. Our toy dataset consisted of 50 networks; the expected successor for a vertex was picked by an author of a highly regarded counterterrorism book and by a retired general in the U.S. Army. We also used four real datasets: (i) Al-Qaeda (101 nodes, 121 edges) built by an Al-Qaeda expert expanding Sageman’s18 data; (ii) Hamas (78 nodes, 139 edges) built by one of the authors, an expert in Hamas analysis; (iii) Hezbollah (60 nodes, 64 edges) built by an outside expert on Hezbollah who has worked extensively in Lebanon and built the dataset from Arabic, English, and French sources; and (iv) Lashkar-e-Taiba (153 nodes, 220 edges) built during the writing of a book on Lashkar-e-Taiba, Computational Analysis of Terrorist Groups: Lashkar-e-Taiba, by two of the authors. All these datasets represent real ground truth. As STONE requires no training, all data was used directly for testing.

Experiment 1. We tested what settings would yield the highest prediction accuracy for the TSP, allowing δ to be 2, 3, 4, or 5%; Figure 13 includes six of the settings we used. The constants αWRP, αPOCC denote the weights of WRP; POCC denotes the weights of WRP and POCC; αrank denotes the rank of a vertex; αhost denotes the hostility of a vertex to the West; αcomp denotes the vertex’s competence carrying out terror attacks; and αBB represents blowback. The numbers in parentheses in Figure 14 are the results returned by the STONE algorithm on average. STONE aims for high accuracy predicting successors of a removed terrorist while presenting as few candidate successors as possible to the analyst. Settings 3 and 4 are best, returning few candidates with over 80% accuracy, even with δ = 2%. Note from settings 3 and 4 that the rank of a candidate seems to be the most important factor, followed equally by his influence (WPR) and strength of network (POCC).

Experiment 2. As measuring the accuracy of STONE-Reshape algorithm by removing real terrorists is infeasible, and no historical ground truth exists for such removal, we tested the algorithm’s accuracy by comparing it against the opinion of counterterror experts who rated the results on a scale of 1–5, with 5 the best. We tested all three lethality functions and all six settings against the Al-Qaeda, Hamas, Hezbollah, and Lashkar-e-Taiba datasets; Figure 15 includes the experts’ levels of satisfaction considering lethality function L3 and all six settings.

Back to Top

Conclusion

STONE addresses the problem of identifying a set of k terrorists in a terrorist organization network whose capture and removal would minimize the expected lethality of the resulting network. To achieve such performance, STONE addresses three problems: terrorist successor; multiple terrorist successor; and terrorist network reshaping. We first developed a method for predicting who would replace a “removed” terrorist. Using four real-world terrorist network datasets, we showed in over 80% of the cases of terrorist turnover, the true replacement of a removed terrorist is identified among those within 2% probability of the most probable replacement predicted by STONE; moreover, this top 2% of candidates contains only, on average, a few terrorists (settings 3 and 4 in Figure 13). We showed how to infer a probability distribution on the possible new networks that result from the removal of a set of terrorists. We used steps one and two to develop the STONE-Reshape algorithm to identify a set of k or fewer individuals to be removed from a network to minimize its operational efficiency. STONE allows analysts to set constraints on who can be removed (such as an analyst could decide certain people should not be removed), what vertex properties should be considered (the analyst can use different properties for different groups), and constraints as to who can replace who.

This work represents a start on the important problem of whom to remove from a terror network. When a vertex is removed, a power struggle may ensue, leading to a split. Can we thus adapt the STONE-Reshape algorithm to predict when such splits will occur? Likewise, a higher-ranked individual may occasionally be moved “down” to fill a spot that opens up when a lower-ranking terrorist is removed. Or, alternatively, the open functional position is allocated to someone with higher rank. We have not considered this possibility here, though it should be addressed. A single group can have multiple subgroups (such as Al-Qaeda in the Islamic Maghreb and Al-Qaeda in the Arabian Peninsula within Al-Qaeda). The relationships between groups and subgroups must thus be explored when identifying how to destabilize an organization. We may not want to destabilize it in a way that actually strengthens one of its more lethal subgroups. There is thus ample opportunity for further research.

We conclude by reiterating the fact that tactical approaches to defeating terrorist operations address the “symptoms” (attacks) of a set of grievances of a terror group. In cases where it is possible to do so, incentives may be tried; for instance, the Rwandan government’s disarmament, demobilization, and reintegration program successfully defanged most of the Hutu militias that carried out the genocide in Rwanda in 1994. However, such efforts have not always been successful. Tactical operations to defeat terror operations must be carried out when an innocent population is at risk from attack, and integration of tactical approaches with strategic incentives to defeat terror groups should be weighed carefully.

Back to Top

Acknowledgment

This article is based on the paper "STONE: Shaping Terrorist Organizational Network Efficiency” in Proceedings of the 2013 IEEE/ACM ASONAM International Conference on Advances in Social Network Analysis and Mining (Niagara Falls, Canada, Aug. 25–28). ACM Press, New York, 2013. The work was partly funded by U.S. Army Research Office grant W911NF0910206.

Back to Top

Back to Top

Back to Top

Back to Top

Figures

F1 Figure 1. Sample terrorist organizational network.

F2 Figure 2. Reshaping the network in Figure 1 following removal of Node B.

F3 Figure 3. Weighted removal PageRank.

F4 Figure 4. WRP of the vertices in the small terrorist network in Figure 1, assuming B is being removed.

F5 Figure 5. Property-oriented clustering coefficient.

F6 Figure 6. Probabilities that vertices C, A, D, E, F from Figure 1 replace B.

F7 Figure 7. Multiple terrorist successor problem and algorithm sketch.

F8 Figure 8. Lethality functions.

F9 Figure 9. Terror network time series.

F10 Figure 10. Substitution diagrams.

F11 Figure 11. Possible terror networks.

F12 Figure 12. Network reshaping algorithm.

F13 Figure 13. Experiments parameter settings.

F14 Figure 14. Experiment 1 results.

F15 Figure 15. Experiment 2 results.

UF1 Figure. Nelly Avila Moreno, a former high-ranking member of Colombia’s Marxist FARC guerrillas, is escorted by soldiers on August 10, 2009, as she arrives at a press conference in Medellin, Colombia, to report on her peace efforts since her surrender.

Back to top

    1. Brin, S. and Page, L. The anatomy of a large-scale hypertextual Web search engine. Computer Networks 30, 1–7 (Apr. 1998), 107–117.

    2. Carley, K.M. Destabilization of covert networks. Computational & Mathematical Organization Theory 12, 1 (Apr. 2006), 51–66.

    3. Carley, K.M., Lee, J.-S., and Krackhardt, D. Destabilizing networks. Connections 24, 3 (2002), 79–92.

    4. Cronin, A.K. How Terrorism Ends: Understanding the Decline and Demise of Terrorist Campaigns. Princeton University Press, Princeton, NJ, 2010.

    5. Gartenstein-Ross, D. Bin Laden's Legacy: Why We're Still Losing the War on Terror. John Wiley & Sons, Inc., New York, 2011.

    6. John, W. Caliphate's Soldiers: The Lashkar-e-Tayyeba's Long War. Amaryllis and the Observer Researcher Foundation, New Delhi, India, 2011.

    7. Krebs, V.E. Mapping networks of terrorist cells. Connections 24, 3 (2002), 43–52.

    8. Kuhn, H.W. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, 1–2 (Mar. 1955), 83–97.

    9. Latora, V. and Marchiori, M. How the science of complex networks can help developing strategies against terrorism. Chaos, Solitons & Fractals 20, 1 (Apr. 2004), 69–75.

    10. Lindelauf, R., Borm, P., and Hamers, H. The influence of secrecy on the communication structure of covert networks. Social Networks 31, 2 (May 2009), 126–137.

    11. Lomborg, B. Is counterterrorism good value for money? NATO Review Magazine (Apr. 2008).

    12. Mannes, A. Profiles in Terror: A Guide to Middle East Terror Organizations. Rowman and Littlefield Publishers, Lanham, MD, 2004.

    13. Memon, B.R. Identifying important nodes in weighted covert networks using generalized centrality measures. In Proceedings of the European Intelligence and Security Informatics Conference (Odense, Denmark, Aug. 22–24). IEEE Computer Society, 2012, 131–140.

    14. Memon, N. and Larsen, H.L. Practical algorithms for destabilizing terrorist networks. In Proceedings of the IEEE International Conference on Intelligence and Security Informatics (San Diego, CA, May 23–24). Springer, 2006, 389–400.

    15. Mendenhall, W. and Sincich, T. A Second Course in Statistics: Regression Analysis. Pearson, Upper Saddle River, NJ, 2011.

    16. Murty, K.G. An algorithm for ranking all the assignments in order of increasing cost. Operations Research 16, 3 (May–June 1968), 682–687.

    17. Ozgul, F., Bondy, J., and Aksoy, H. Mining for offender group detection and story of a police operation. In Proceedings of the Sixth Australasian Conference on Data Mining and Analytics (Gold Coast, Australia, Dec. 3–4). Australian Computer Society, Sydney, 2007, 189–193.

    18. Sageman, M. Understanding Terror Networks. University of Pennsylvania Press, Philadelphia, 2004.

    19. Subrahmanian, V., Mannes, A., Sliva, A., Shakarian, J., and Dickerson, J. Computational Analysis of Terrorist Groups: Lashkar-e-Taiba. SpringerLink: Bücher. Springer London, Ltd., 2012.

    20. Tankel, S. Storming the World Stage: The Story of Lashkar-e-Taiba. C. Hurst & Co. (Publishers) Ltd., London, U.K., 2011.

    21. Watts, D.J. and Strogatz, S.H. Collective dynamics of 'small-world' networks. Nature 393, 6684 (June 4, 1998), 440–442.

    a. Though Lakhvi remains in a Pakistani jail for his role in the 2008 Mumbai, India, attacks, news sources report he is directing operations from jail.

    b. The numerator is the number of pairs of vertices within k distance units from v that are directly connected and have properties in P; the denominator is the total number of neighbors of v having all properties in P that are within k distance units of v. The ratio provides the desired quantity.

    c. The values of rank and capacity are scaled with respect to their maximum value.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More