Reshaping Terrorist Networks

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

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.¹¹ 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.¹⁹ However, strategic defeat of terrorist organizations is rare, despite some notable successes (such as the Provisional IRA in Ireland and Aum Shinrikyo in Japan).⁴ 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,¹² Hezbollah,¹² 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.⁵ 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 p_max of succeeding r, as well as all terrorists whose probability of succeeding r was “close enough” (within 2%, 3%, 4%, or 5% of p_max). 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, Memon¹³ used traditional centrality measures to identify key actors, and Memon and Larson¹⁴ defined efficiency of a network using prior work of Latora and Marchiori.⁹ Memon and Larsren¹⁴ proposed a position role index to distinguish between gatekeepers and followers in such networks and define “dependence centrality,” or DC. Memon and Larsen¹⁴ showed the values of DC on Krebs’s 9/11 network.⁷ Carley³ 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. Carley² suggested “isolation” strategies yielding valuable “objective functions” can be used within the lethality measures described here. Ozgul¹⁷ studied the problem of detecting cells in terror networks, proposing such algorithms as GDM and OGDM. Lindelauf¹⁰ 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 PageRank¹ 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 coefficients²¹ 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 p_i 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

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.2), POCC with k = 2, and P = Ø (with α₁ = 0.2), the node rank (with α₂ = 0.4), and node capacity (α₃ = 0.2).^c The possible candidates to replace vertex r = B are then:

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:

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 X_R for a set R of vertices being removed with respect to condition C is a set of pairs (r, c_r) (r being a removed vertex and c_r being its replacement) satisfying four conditions:

1. Every removed vertex has a replacement. For each r ∈ R, there is a pair (r, c_r) ∈ X_R and
2. Replacement vertices cannot be removed. {c_r | (r, c_r) ∈ X_R} ⊆ (V – R) and
3. Replacement nodes must be candidates. For each pair (r, c_r) ∈ X_R, c_r 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, c_r), (r′, c_r) are both in X_R.

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 X_R with respect to R and C. The probability P(X_R) that X_R will in fact be the replacement for R is simply the product of the individual probabilities (c_r, r) that c_r 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 (B, C) = 0 and (A, C) = 1, and (D, B) = 0.31 and (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 X_max 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 X_max to the analyst. Rather, STONE returns all candidate replacement sets X_R whose probability is at most δ percentage points smaller than X_max‘s probability (see Figure 7). Note X_max is not an input to this problem; STONE algorithms solve it automatically without having X_max as an input. STONE developers prove MTSP can be solved in polynomial time by leveraging an efficient algorithm due to Murty¹⁶ 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,¹⁶ STONE algorithms enumerate, in decreasing order of probability, all solutions to the maximal matching, until STONE reaches a solution X_R such that (X_max) – (X_R) > δ.

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: L₁ assesses the difference of ranks of violent-prone and violence-adverse node; L₂ modulates L₁ by degree of the vertices involved; L₃ modulates L₁ by using WRP instead of degree; and L₄ uses regression to correlate L₁, L₂, and L₃ 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.

L₁ 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, L₁(ON) = wt(A) + wt(B) + wt(D) – wt(C) – wt(E) – wt(F) = 1.

L₂ 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 L₂(ON) = 48, while L₃(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 ON₀ for some period I₁ of time at which time terrorist r₁ was removed, leading to network ON₁. After time period I₂, a terrorist r₂ was removed, leading to network ON₂. During each period I_j, the group launched some number A_j of attacks. The variables A_j are measures of the lethality of the network N_j–1. For each group, we were thus able to build a table. The jth row of this table corresponded to the time period I_j and the columns contained the values of L₁(ON_j), L₂(ON_j), L₃(ON_j) as independent variables and A_j as a dependent variable. Using standard multivariate regression analysis,¹⁵ we learned a hybrid lethality function L_h relating the values returned by L₁, L₂, L₃ 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 L_h 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 L_h from the smaller Al-Qaeda dataset, the Pearson correlation coefficient between the actual number of Al Qaeda attacks and our predictions was 0.652. L_h 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 C₁, …, C_n using the definition given earlier. Each C_i is a child of R with the probability p_i labeling the link, where p_i is the probability that C_i replaces R. If C_i were to replace R, STONE would need to find a replacement for the set C_i of vertices. Figure 10a outlines this relationship through an example where C₁ has two possible candidate replacements—D₁ and D₂. Likewise, C₂, which is a candidate set to replace R, has only one candidate to replace it—D₂; 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, C₂, D₂ represents the removal of R from the network, its replacement by C₂, and replacement of C₂ by D₂. Every PRC X₁, …, X_m generates a PTN as follows: Starting with the terrorist network ON, let ON₁ be the network obtained by replacing R with X₁ in network ON. Similarly, let ON₂ be the result of replacing X₁ in network ON₁ by X₂. STONE does this repeatedly until X_m–1 in ON_m–1 is replaced with X_m. 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—N₁ and N₂ (see Figure 11). The probability of a PTN with respect to a path is the product of the probabilities labeling the edges. The probability (N₂) of the PTN N₂ 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 D₂ 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

Returning to our running example, the lethality L₂ of the possible network N₁ is L₂(N₁) = 17 while L₂(N₂) is 2. The expected lethality is then LEV(ON,R) = Σ_{N∈PTN(ON,R)} (N) · L₂(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 r ∈ R satisfies condition C and
3. There is no set R′ of vertices satisfying (i) and (ii) such that L_EV (ON, R′) < L_EV(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 L₃ 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’s¹⁸ 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 L₃ 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

Back to top