k Fragility Maximization Problem to Attack Robust Terrorist Networks
 Author: Thornton Jabre L., Kim Donghyun, Kwon SungSik, Li Deying, Tokuta Alade O.
 Organization: Thornton Jabre L.; Kim Donghyun; Kwon SungSik; Li Deying; Tokuta Alade O.
 Publish: Journal of information and communication convergence engineering Volume 12, Issue1, p33~38, 31 March 2014

ABSTRACT
This paper investigates the shaping operation problem introduced by Callahan et al., namely the
k fragility maximization problem (k FMP), whose goal is to find a subset of personals within a terrorist group such that the regeneration capability of the residual group without the personals is minimized. To improve the impact of the shaping operation, the degree centrality of the residual graph needs to be maximized. In this paper, we propose a new greedy algorithm fork FMP. We discover some interesting discrete properties and use this to design a more thorough greedy algorithm fork FMP. Our simulation result shows that the proposed algorithm outperforms Callahan et al.'s algorithm in terms of maximizing degree centrality. While our algorithm incurs higher running time (factor ofk ), given that the applications of the problem is expected to allow sufficient amount of time for thorough computation andk is expected to be much smaller than the size of input graph in reality, our algorithm has a better merit in practice.

KEYWORD
Graph algorithm , Social networking , Terrorist networks

I. INTRODUCTION
Over years, terrorist organizations have proven their superior capability to establish a new leadership after the current one is disorganized. Callahan et al. [1] introduced the concept of the shaping operation on a network of terrorists to reduce its leadership recovery capability. The authors noticed that the degree centrality (see Definition 1) of the network is a good metric to evaluate the criticality of the highest degree node (the leader) in it. It is known that a network with higher degree centrality is more likely to be dismantled after the highest degree node is removed. A shaping operation aims to remove at most
k nodes from the network, wherek is the maximum number of targets which can be eliminated by available resources, such that the degree centrality of the residual network is maximized. Clearly, such preemptive shaping operation on a terrorist network will maximize the effectiveness of the followup attack over the target with highest value (e.g., the leader) in the residual network. Callahan et al. [1] formulated the problem of computing such subset as “Fragility”. During the rest of this paper, we will refer this problem as thek fragility maximization problem (k FMP) for the simplicity of our discussion (see Definition 2).Callahan et al. [1] also showed that
k FMP is NPhard and proposed a greedy heuristic algorithm for it. In this paper, we propose a new heuristic algorithm fork FMP. We first prove an optimal solution ofk FMP can be obtained by solving its variation, Ek FMP whose goal is to find “exactly”k nodes (instead of at mostk nodes) from a given network such that the degree centrality of the residual network is maximized. Then, we propose a new greedy strategy for Ek FMP. Using this result, we can construct a heuristic algorithm fork FMP. Via simulation, we compare our heuristic algorithm fork FMP with the greedy algorithm by Callahan et al. [1] as well as an optimal solution.The rest of this paper is organized as follows. Section II provides some preliminaries including several important definitions and lemmas. Section III presents our main results which include our new greedy heuristic algorithm for
k FMP. We present the simulation results and corresponding analysis in Section IV. Finally, we conclude this paper in Section V.II. PRELIMINARIES
In this paper,
G = (V, E ) represents a social network graphG with a vertex setV =V(G) and a bidirectional (or equivalently undirected) edge setE = E(G) . We usen to denote the number of vertices inV , i.e.,n = V . For eachv_{i} ∈v , Δv_{i} (G ) is the degree ofv_{i} , inG , which is the number of edges adjacent tov_{i} inG . Likewise, the degree ofG is the degree of a node with the largest degree inG , i.e., Given a node subsetV' ⊆V ,G [V' ] is a subgraph ofG induced byV' . Now, we introduce several important definitions including the formal definition of the problem of our interest, thek FMP as well as some important lemmas.Definition 1 (Degree Centrality [2]).Given a graph G = (V, E ),the degree centrality of G is defined as Definition 2 (k FMP [1]).Given a graph G = (V, E) and a positive integer k ,k FMPis to find a subset V' ⊂ V whose size is no greater than k such that C_{G'}, the degree centrality of G' = G[V\V'] = G[V − V'] is maximized. To simplify our discussion, we rewrite the definition of
k  FMP in Definition 2 as below (Definition 3).Definition 3 .Given a graph G = (V, E) and a positive integer k, k FMPis to find a subset V' ⊂ V whose size is no greater than k such that the degree centrality of the residual graph after removing V' from V , i.e.,is maximized .Now, consider E
k FMP, a variation ofk FMP in which the size ofV' has to be exactlyk , i.e., we are required to remove exactlyk nodes. Then, in Eq. (2), V'  is a constant number and independent from our choice ofV' , which implies (V\V' − 1)(V\V'  − 2) is a constant number, either. As a result, the degree centrality ofG' =G[V\V'] is solely dependent onsince
n = V  andk = V' . Therefore, to maximize the degree centrality ofG [V\V' ], we have to find aV' such that the formulation in the right side of the equality in Eq. (3), say the “modified degree centrality”, is maximized. Now, we provide the following lemma and corollary.Lemma 1. Suppose we have a γapproximation algorithm to solve Ek FMPin which the size of a V' has to be exactly k. Then, there exists a γapproximation algorithm fork FMP.Proof. We can solvek FMP by (a) gradually increasingl from 1 tok by 1, and for eachl , applying the γ approximation algorithm for Ek FMP withk = l and obtain a subsetV' ⊆V , and (b) selecting the best solution among thek cases, i.e.,V′_{l} such that the degree centrality ofG[V\V'_{l}] becomes maximum.Now, we show that this strategy is a γapproximation algorithm for
k FMP. Suppose OPT_{1}, …, OPT_{k} is an optimal solution of Ek FMP with differentk = l . Suppose D(OPT_{l}) is the degree centrality achieved by OPT_{l} . Likewise, let D(F_{l} ) be the degree centrality achieved by F_{l} , where F_{l} is an output of the Step (a) of the algorithm described above withk = l. Since we use the γapproximation algorithm for Ek FMP withk = l , for eachl , we haveConsider an optimal solution OPT of
k FMP. Then, we have to have D(OPT_{p} ) = D(OPT) for somep , 1 ≤p ≤k . Furthermore, by our strategy, we pick F_{q} with largest D(F_{q} ). As a result, we haveand thus lemma holds true.
Corollary 1. An optimal solution of Ek FMPcan be used to recover an optimal solution of k FMP.Proof. This proof of this corollary naturally follows from Lemma 1 by replacing γ = 1 for an exact algorithm Ek  FMPIII. A NEW GREEDY ALGORITHM FOR
k FMPIn this section, we introduce a greedy strategy for E
k  FMP and use this to build a heuristic algorithm fork FMP following the idea in Lemma 1 and Corollary 1. GreedyEk  FMP (Algorithm 1) is our greedy algorithm for Ek FMP. The core strategy of this algorithm based on the modified degree centrality in Eq. (3). To construct a set ofk nodesV' fromV , this algorithm iteratively selects a node fromV\V' toV' , which is initially an empty set such that the modified degree centrality ofG[V\V'] is maximized.Now, using the idea in Lemma 1 and Corollary 1 combined with GreedyE
k FMP, we construct MaxFragility, a heuristic algorithm fork FMP. Remind that by definition, Ek FMP is a variation ofk FMP, in a way that in Ek FMP,k is a fixed input parameter, which is not true ink FMP. Therefore, to solvek FMP using GreedyEk FMP, we varies the size l ofV' from 1 tok and computek differentV' _{l} ′s, each of whose size is 1, 2, …,k . Then, we pickV' _{l} such that the modified degree centrality ofG[V\V'] is the maximum. MaxFragility (Algorithm 2) is the formal definition of this strategy to solvek FMP.IV. SIMULATION RESULTS
In this section, we compare the performance of Max Fragility and Callahan et. al. [1] algorithm for
k FMP via simulation. For this simulation, we assumen nodes, wheren = 100, 150, 200, 250, 300 and randomly establish edges between each pair of nodes with a probability ofp , wherep = 75%, 85%, 95%. Then, we varyk = 10, 20, 30 and execute each algorithm on each graph instance. For each parameter setting, we repeat 10 and obtain averaged centrality value achieved by each algorithm as well as running time.> A. Degree Centrality Comparison
In Fig. 1, we fix
p and varyk andn for each algorithm and see how each algorithm behaves in terms of the degree centrality of the output. Both algorithms show that as the number of nodes increases, the degree centrality goes down. At the same time, with largerk , the degree centrality of the output is higher.In Fig. 2, we compare the performance of the algorithm with
p = 85%,k = 20, and variablen . As we can see, our MaxFragility outperforms Callahan et al. [1] in terms of degree centrality.In Fig. 3, we compare the performance of the algorithm with
p = 85%,n = 200, and variablek . From this figure, we can observe that the performance gap between our Max Fragility and Callahan et al. [1] is getting larger ask grows.In Fig. 4, we compare the performance of the algorithm with
n = 200,k = 20, and variablep . From this figure, we can observe that the performance gap between our Max Fragility and Callahan et al. [1] is getting larger as the density of the network grows.Finally, in Table 1, we compare the performance of Max Fragility and Callahan et al. [1] against the optimal solution which is computed by an exhaustive search. As we can see from the table, our algorithm roughly achieve 50% of the centrality which is achieved by the optimal solution while Callahan et al. [1]’s achieved 25%. In summary, Max Fragility always outperforms Callahan et al. [1] regardless from the parameter setting. Their performance gap becomes larger as
k andp increases.> B. Running Time Analysis
Next, we compare the running time of the algorithms. The simulation is conducted using an Apple MacBook with 2.4 GHz Intel Core 2 Duo CPU, 4 GB 1067 MHz DDR3 Memory, and OS X 10.8.5. GCC++ version 4.2 is used for implementation.
In Fig. 5, we set
p = 85%,k = 10, 20, 30, andn = 100, 150, 200, 250, 300, and measure the running time of each algorithm in second. As we can see, the running time of both algorithms increases as the number of nodesn increases.It is easy to see that the running time of MaxFragility is
O(k) times larger than that of Callahan et al. [1]. In Fig. 6, we setp = 85%,k = 20, andn = 100, 150, 200, 250, 300, and measure the running time of each algorithm. As we can see, asn increases, MaxFragility requires more time for computation.In Fig. 7, we set
p = 85%,n = 200, and varyk to see its impact. As we can see, as k increases, MaxFragility takes more time than Callahan et al. [1]. While our MaxFragility takes more time, however, the applications of the problem of our interest (i.e., dismantling a terrorist group) do not require urgent near realtime computation, but more precise computation to improve the degree centrality, it is reasonable to claim that our MaxFragility has a better merit than Callahan et al. [1]’s algorithm in reality.V. CONCLUSION
In this paper, we introduce a greedy algorithm for the
k  FMP which is initially introduced by Callahan et al. [1]. By exploiting some discrete properties, we were able to design a new greedy algorithm fork FMP. Our simulation results show our algorithm outperforms Callahan et al.’s in terms of the quality of the solution in the exchange of slightly increased running time (a factor of a given constantk ). Considering the applications in which we are expected to have a plenty amount of time for more thorough computation, we believe that our algorithm has a more practical merit. As a future work, we plan to investigate an approximation algorithm for this interesting NPhard optimization problem.

[Fig. 1.] Performance of each algorithm with p = 85%, k = 10, 20, 30, and n = 100, 150, 200, 250, 300. (a) MaxFragility and (b) Callahan et al. [1].

[Fig. 2.] Performance comparison with p = 85%, k = 20, and n = 100, 150, 200, 250, 300.

[Fig. 3.] Performance comparison with p = 85%, k = 10, 20, 30, and n = 200.

[Fig. 4.] Performance comparison with p = 75%, 85%, 95%, k = 20, and n = 200

[Table 1.] Performance comparison against optimal solution with n = 50, k = 10, p = 85%

[Fig. 5.] Running time of each algorithm with p = 85%, k = 10, 20, 30, and n = 100, 150, 200, 250, 300. (a) MaxFragility and (b) Callahan et al. [1].

[Fig. 6.] Running time comparison with p = 85%, k = 20, and n = 100, 150, 200, 250, 300.

[Fig. 7.] Running time comparison with p = 85%, n = 200, and k = 10, 20, 30.