Contributed articles
# 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.

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 rankcoded 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 *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.

Identifying key actors in networks is studied through centrality measures; for example, Memon^{13} used traditional centrality measures to identify key actors, and Memon and Larson^{14} defined efficiency of a network using prior work of Latora and Marchiori.^{9} Memon and Larsren^{14} proposed a position role index to distinguish between gatekeepers and followers in such networks and define "dependence centrality," or DC. Memon and Larsen^{14} showed the values of DC on Krebs's 9/11 network.^{7} Carley^{3} 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^{2} suggested "isolation" strategies yielding valuable "objective functions" can be used within the lethality measures described here. Ozgul^{17} studied the problem of detecting cells in terror networks, proposing such algorithms as GDM and OGDM. Lindelauf^{10} 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.

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.

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 propertiesWRP and POCCused 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 himhis 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^{1} 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^{21} 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-Taibaif the current operations chief Zakiur-Rehman Lahkhvi is removedmight 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} = 0.2), POCC with *k* = 2, and ** P** = Ø (with

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.

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:

*Every removed vertex has a replacement*. For each*r**R*, there is a pair (*r, c*_{r})*X*_{R}and*Replacement vertices cannot be removed*. {*c*_{r}| (*r, c*_{r})*X*_{R}} (*V R*) and*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*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^{16} 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 *X*_{R} such that (*X*_{max}) (*X*_{R}) > .

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*_{1} assesses the difference of ranks of violent-prone and violence-adverse node; *L*_{2} modulates *L*_{1} by degree of the vertices involved; *L*_{3} modulates *L*_{1} by using WRP instead of degree; and *L*_{4} uses regression to correlate *L*_{1}, *L*_{2}, and *L*_{3} 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*_{1} 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*_{1}(*ON*) = *wt*(*A*) + *wt*(*B*) + *wt*(*D*) *wt*(*C*) *wt*(*E*) *wt*(*F*) = 1.

*L*_{2} 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*_{2}(*ON*) = 48, while *L*_{3}(*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*_{0} for some period *I*_{1} of time at which time terrorist *r*_{1} was removed, leading to network *ON*_{1}. After time period *I*_{2}, a terrorist *r*_{2} was removed, leading to network *ON*_{2}. 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 *j*th row of this table corresponded to the time period *I*_{j} and the columns contained the values of *L*_{1}(*ON*_{j}), *L*_{2}(*ON*_{j}), *L*_{3}(*ON*_{j}) as independent variables and *A*_{j} as a dependent variable. Using standard multivariate regression analysis,^{15} we learned a hybrid lethality function *L*_{h} relating the values returned by *L*_{1}, *L*_{2}, *L*_{3} 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 (19902012) and Al Qaeda dataset (20012013). 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.

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*_{1}, ..., *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*_{1} has two possible candidate replacements*D*_{1} and *D*_{2}. Likewise, *C*_{2}, which is a candidate set to replace *R*, has only one candidate to replace it*D*_{2}; 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*_{2}, *D*_{2} represents the removal of *R* from the network, its replacement by *C*_{2}, and replacement of *C*_{2} by *D*_{2}. Every PRC *X*_{1}, ..., *X*_{m} generates a PTN as follows: Starting with the terrorist network *ON*, let *ON*_{1} be the network obtained by replacing *R* with *X*_{1} in network *ON*. Similarly, let *ON*_{2} be the result of replacing *X*_{1} in network *ON*_{1} by *X*_{2}. `STONE`

does this repeatedly until *X*_{m}1 in *ON*_{m1} 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*_{1} and *N*_{2} (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*_{2}) of the PTN *N*_{2} 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*_{2} 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*_{2} of the possible network *N*_{1} is *L*_{2}(*N*_{1}) = 17 while *L*_{2}(*N*_{2}) is 2. The expected lethality is then LEV(*ON*,*R*) = _{NPTN(ON,R)} (*N*) · *L*_{2}(*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

- |
*R*|*k*and - Each
*r**R*satisfies condition*C*and - 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*_{3} and *k* = 2, Algorithm 1 suggests removing *D* and *F*, decreasing the expected network lethality to 8.87.

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^{18} 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 15, 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*_{3} and all six settings.

`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.

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. 2528). ACM Press, New York, 2013. The work was partly funded by U.S. Army Research Office grant W911NF0910206.

1. Brin, S. and Page, L. The anatomy of a large-scale hypertextual Web search engine. *Computer Networks 30*, 17 (Apr. 1998), 107117.

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

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

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), 4352.

8. Kuhn, H.W. The Hungarian method for the assignment problem. *Naval Research Logistics Quarterly 2*, 12 (Mar. 1955), 8397.

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), 6975.

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), 126137.

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. 2224). IEEE Computer Society, 2012, 131140.

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 2324). Springer, 2006, 389400.

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 (MayJune 1968), 682687.

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. 34). Australian Computer Society, Sydney, 2007, 189193.

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), 440442.

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.

Figure 1. Sample terrorist organizational network.

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

Figure 3. Weighted removal PageRank.

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

Figure 5. Property-oriented clustering coefficient.

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

Figure 7. Multiple terrorist successor problem and algorithm sketch.

Figure 8. Lethality functions.

Figure 9. Terror network time series.

Figure 10. Substitution diagrams.

Figure 11. Possible terror networks.

Figure 12. Network reshaping algorithm.

Figure 13. Experiments parameter settings.

Figure 14. Experiment 1 results.

Figure 15. Experiment 2 results.

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.

**©2014 ACM 0001-0782/14/08**

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from permissions@acm.org or fax (212) 869-0481.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.

No entries found