Computational Analysis of Connectivity Games with Applications to the Investigation of Terrorist Networks

1 Introduction

Facing, on the one hand, the increased size of terrorist groups and, on the other hand, inevitable budget cuts, security agencies urgently require efficient techniques to identify who plays the most important role within a terrorist network and, therefore, where scarce resources should predominantly be focused. In this context, a number of authors have proposed using social network analysis to investigate terrorist organisations (e.g., [Carley et al., 2003; Krebs, 2002; Farley, 2003; Lindelauf et al., 2013; Ressler, 2006]). Analyst's Notebook 8 [I2, 2010]-a software package used worldwide by law enforcement and intelligence agencies-has recently included standard centrality metrics for networks (graphs), such as degree, closeness and betweenness centralities [Brandes and Thomas, 2005; Friedkin, 1991]. But the usefulness of these metrics for terrorist networks is limited as they are often Talal Rahwan and Nicholas R. Jennings University of Southampton, UK

Oskar Skibski

University of Warsaw, Poland

Michael J. Wooldridge

University of Oxford, UK

unable to capture the complex nature of these organisations [Lindelauf et al., 2013].

Recently, in an attempt to address these shortcomings, Lindelauf et al. [2013] developed a more advanced method specifically designed to measure centrality in terrorist networks. The new method belongs to a class of so-called Shapley value-based centrality metrics 1 and builds upon the notion of coalitional connectivity games proposed by Amer and Gimenez [2004].

Unfortunately, the computational aspects of connectivity games by Amer and Gimenez have not been studied to date. This means that the current use of Lindelauf et al.'s method is limited only to small terrorist networks (of 25 members or so) because general-purpose algorithms for coalitional games have to be applied, which exhaustively search the space of all possible coalitions. Thus, they are inapplicable to many realworld applications such as the terrorist networks responsible for the WTC 9/11 attack (of 35, 63 or more nodes depending on the considered type of links between terrorist).

Against this background, we provide in this paper the first computational analysis of connectivity games proposed by Amer and Gimenez:

• We prove that computing the Shapley value in connectivity games-including the centrality metrics of Lindelauf et al.-is #P-Hard.
• We propose a dedicated exact algorithm for computing these centrality metrics. While the general-purpose Shapley value algorithm requires checking all subsets of vertices in the graph, our algorithm traverses through (most often) much smaller number of connected subgraphs. It also has minimal memory requirements.
• We test our algorithm by analysing the aforementioned WTC 9/11 terrorist network with 36 members and 125 identified connections. In this setting, our algorithm returns the solution within 38 minutes, compared to weeks if a general-purpose approach was applied.

1 See the next section for more details.

• In order to study even bigger networks, we propose a dedicated approximate algorithm based on Monte Carlo sampling.

2 Connectivity Games for Terrorist Networks

Terrorist networks have been recently modelled using a weighted graph, G, composed of vertices (or nodes, i.e., individual terrorists) and labelled edges [Carley et al., 2003; Krebs, 2002; Farley, 2003; Lindelauf et al., 2013; Ressler, 2006]. Based on available intelligence, an edge represents, for instance, a communication link between two terrorists, and the weight of the edge represents the frequency with which that link is used. Weights can be associated not only with edges but also with vertices. This, as argued by Lindelauf et al., allows for modelling additional information that intelligence agencies gather on individuals within the network.

We will denote the set of all vertices in the graph by V (G) and the set of all edges by E(G), respectively, where every edge in E(G) connects two vertices in V (G). An edge connecting vertices vi, vj ∈ V (G) will be denoted (vi, vj), and its label (or weight) will be denoted ω(i, j) ∈ Ω(G). The weight of vertex vi ∈ V (G) will be denoted γ(i) ∈ Γ(G).

To address the limitations of standard centrality metrics, Lindelauf et al. proposed a new metric that builds upon connectivity games by Amer and Gimenez [2004]. In these coalitional games on graphs, all subsets of set V (G) are considered to be possible coalitions of terrorists. Apart from the empty set, every single coalition is classified as belonging to either the set of connected coalitions (denoted C(G)) or disconnected coalitions (denoted ˜ C(G)). We say that C is connected if between any two nodes in C there exists at least one path of which all nodes belong to C. Otherwise C is disconnected. Importantly, any two terrorists in a connected coalition are able to communicate with each other (via a path), whereas in a disconnected coalition this is not the case. In many connected coalitions, from this point of view, some nodes play more important role than others, as their removal makes a coalition disconnected. We will call them pivotal.

To complete the definition of the connectivity game, we need to specify a so-called characteristic function-in coalitional games this function, ν : 2V → R, assigns to every coalition C ⊆ V a numerical value representing its performance (by convention, it is assumed that ν(∅) = 0). In their games, Amer and Gimenez assign to every connected coalition a value of 1, and to disconnected coalitions a value of 0. Lindelauf et al. extend this definition by assuming that values of connected coalitions may depend on the network in a variety of ways, i.e., they can be a function of adjacent edges or nodes, their weights, etc. More formally:

The exact definition of f depends on the availability of information and analytical needs. 2 For instance, to analyse the Jemaah Islamiyah network responsible for the 2002 Bali attack in Indonesia, Lindelauf et al. assume:

2 We will write V , E, C, f(C) instead of V (G), E(G), C(G),

where E(C)={(vi, vj)∈E | vi, vj ∈C} denotes the set of edges between players in C; that is f equals the number of edges in the connected coalition divided by their weight).

Since the goal of a centrality metric is to create a ranking of nodes, the question now is how to evaluate the importance of an individual node given all the roles that such a node plays in the entire connectivity game. To this end, Lindelauf et al. proposed to apply the Shapley value-one of the fundamental concepts in cooperative game theory. Specifically, Shapley [1953] proposed to evaluate the role played by individual players in a coalitional game by comparing their marginal contributions to every possible coalition. In order to formalize this concept in the terrorist network context, let π ∈ Π(V ) denote a permutation of nodes in V , and let C π i denote the coalition made of all predecessors of node vi in π. More formally, if we denote by π(j) the location of vj in π, then: C π i = {vj ∈ π : π(j) < π(i)}. The Shapley value of vi, denoted SVi(νf), is then defined as the average marginal contribution of vi to coalition C π i over all π ∈ Π:

where mci(C) = νf (C ∪ {vi}) - νf (C) is the marginal contribution of vi to C ⊆ V . The higher an average contribution of a player to the game is, the higher the Shapley value becomes. This means that, if the coalitional game defined over a network meets certain desired properties, the Shapley value of this game can be used as a centrality metric that rates individual nodes with respect to these properties. In our context of the connectivity game, individual terrorists are rated with respect to the role they play in connecting various, possibly multiple, parts of the network.

Lindelauf et al. argue that the centrality ranking based on the Shapley value of the connectivity game is more effective than degree, closeness and betweenness centralities in exposing the key players in the Bali attack. For example, Azahari bin Husin-the network bomb expert who was considered the "brain" behind the entire operation-is ranked rather low by standard centralities but according to Lindelauf et al. metric is among top five Bali terrorists. Similarly, Feri (Isa)-again ranked low by standard centralities-was, in fact, the suicide bomber. Lindelauf et al. ranked him third.

The formula in (3) can also be stated in the equivalent form:

where ξC = |C|!(|V |-|C|-1)! |V |! . Although it is clearly not possible to escape O(2|V | ) complexity for a general case of a coalitional game, i.e., 2V → R, a number of authors showed that for some games defined on networks, it is possible to take advantage of the network structure and compute. the Shapley value in polynomial time [Deng and Papadimitriou, 1994; Aadithya et al., 2010; Szczepa´nski et al., 2012]. In the next section we will show that this is not the case for connectivity games defined by Amer and Gimenez.

f(C, G), etc., wherever G is clear from the context.

3 Computational Analysis &Algorithms

In this section, we first discuss the complexity of computing the centrality metrics of Lindelauf et al.. We then present our exact and approximate algorithms.

Complexity

First we show that, even for the simplest definition of the connectivity game, where ∀C∈C(G)f(C,G) = 1, computing the Shapley value in an efficient way is impossible. The main problem of interest is as follows:

Definition 2 #CG-SHAPLEY: Given a connectivity game on graph G, where ∀C∈C(G)f(C, G) = 1, we are asked to compute the Shapley value for each node in this graph.

In the first step, let us introduce the following problem:

Definition 3 #CONNECTED-SPANNING-SUB (#CSS): Given a graph G, we are asked to compute the number of connected spanning subgraphs in G.

This problem is #P-Complete even for bipartite and planar graphs [Welsh, 1997]. We will use this hardness result to prove #P-Completeness of the following problem:

Definition 4 #CONNECTED-INDUCED-SUB (#CIS):

Given a graph G, we are asked to compute the number of connected induced subgraphs in G.

Theorem 1 #CONNECTED-INDUCED-SUB is #P-Complete.

Proof of Theorem 1 3 We note first that it is possible to check in polynomial time if a given subgraph is induced and connected. Thus, since a witness can be verified in polynomial time, this problem is in #P. Now, we will reduce a #CSS instance to #CIS. To this end, given a graph G = (V,E), we will construct a transformed graph G′ and show that determining the number of connected induced subgraphs in G′ allows us to easily compute the number of connected spanning subgraphs in G.

Our transformed graph G' is constructed by adding to each edge in G an extra node. Then, to each node from original graph G we attach a clique KA with A nodes. This reduction is shown in Figure 1. More formally we define the following graph G′ :

3 We would like to thank Colin McQuillan from The University of Liverpool who develop the sketch of this proof.

Now, we arbitrarily choose some connected induced subgraph F of G′ . Either this subgraph intersects with the original set of vertices V (G), or it does not. In the latter case, subgraph F is contained within the single copy of KA and there are exactly |V (G)|(2A - 1) such subgraphs. In the former case, we can define some pseudograph F ′ , which consists of the following sets of vertices and edges: 4 V (F ′ ) = V (F) ∩ V (G) and E(F ′ ) = {(u, v) : uv ∈ V (F ) ∧ (u, v) ∈ E(G)}. Note that since F is connected, F ′ also has to be connected. There are exactly 2|V (F ′ )|A choices of F that can give us a particular pseudograph F ′ . Now, we can compute:

which denotes the number of induced connected subgraphs in G′ . The crucial observation here is that, if V (F ′ ) = V (G), then F ′ is a connected spanning subgraph of G. This holds because F is an induced connected subgraph. Now, let N denote the number of spanning connected subgraphs in G. Then, we can rewrite (5) as:

In order to compute N we would like to bound the expression X = M - N(2|V (G)|A). This expression is the number of induced connected subgraphs in G′ that do not correspond to any connected spanning subgraph in G. We have:

where the number 2|V (G)|+|E(G)| is an upper bound on the number of all subgraphs in G. Now, we can use these bounds to transform equation (6) and to get the approximation of N:

In order to deal with the expression |V (G)|+2|V (G)|+|E(G)| 2A we take A > log(|V (G)| + 2|V (G)|+|E(G)| ) so that this fraction becomes smaller than 1. We note that A is bounded by a polynomial in the order of the input G. Then, the number of spanning connected subgraphs of G is the least integer N such that N ≥ M 2A|V (G)| . This is easy to compute given the number of connected induced subgraphs F of G′ . □

4 We note that this tuple is not necessarily a properly defined graph, since it can contain some edge (u, v) and does not contain node v.

From Theorem 1, it trivially follows that the next problem is also #P-Complete:

Definition 5 #CONNECTED-INDUCED-SUB-k (#CIS-k):

Given a graph G, we are asked to compute the number of connected induced subgraphs of size k in G.

Clearly, if we can find in polynomial time an answer for the #CIS-k problem, we could efficiently compute #CIS. Now, the #P-Hardness of #CG-SHAPLEY will be shown by the reduction from #CIS-k:

Theorem 2 #CG-SHAPLEY is #P-Hard.

Proof of Theorem 2: We construct a proof by reduction. In particular, we demonstrate that if there exists an algorithm for solving #CG-SHAPLEY in polynomial time, then it is possible to solve #CIS-k in polynomial time. This contradicts the fact that #CIS-k is #P-complete. Now, we will reduce #CIS-k to #CG-SHAPLEY.

Let G = (V, E) be an arbitrary graph, where |V | = n and |E| = m. We extend the set of nodes of G by a single node v, while the set of edges remains unchanged. In other words, we obtain a new graph G0 by adding a single node not connected to any node from G. Now, from the definition of connectivity games, we note that the marginal contribution of the new node v to any coalition C ⊆ G is either 0 or -1. More specifically, it is -1 if C is connected, and 0 otherwise. Based on this, the Shapley value of node v can be computed as follows, where cGs is the number of connected induced subgraphs in G that contain exactly s nodes:

Now, let us consider a new graph Gi constructed by adding to G the set of i nodes in addition to the node v, while keeping the set of edges just as in G. Analogously to G0, the Shapley value of v in Gi is:

This equation holds because each coalition containing more than n nodes is disconnected, and so the contribution of v to every such coalition is 0. Now, we can build a system of linear equations using each equation (7) from graph Gi, where i ∈ {0, . . . , n}. More precisely, we need to solve the following equation:

that can also be written as Ax = b.

This equation has a unique solution if and only if the determinant of the matrix A is non-zero. We can use Theorem 1.1 from [Bacher, 2002] to prove that it is non-zero. Thus, if we can compute in polynomial time the Shapley value for connectivity games, we would be able to solve this equation and determine all cGi values. Specifically, we can use Gaussian elimination, which works in O(n3 ) time complexity.

We note that the largest possible number in our matrices is n!n!. According to the analysis in (Proposition 2)[Aziz et al., 2009] it is possible to store such a number in km2 (logm)2 bits. It is shown in (Theorem 4.10) [Korte and Vygen, 2005] that in Gaussian elimination each number occurring during the algorithm process can be stored in the number of bits quadric of the input size. □

Analysis of Marginal Contribitions

In this section, we analyse how node vi ∈ V can marginally contribute to coalition C ⊆ V \ {vi}. Four general cases, depicted in Figure 2, can be distinguished:

• (a) Node vi can join a connected coalition C ∈ C and the resulting coalition is also connected, i.e., C ∪ {vi} ∈ C. Here, the marginal contribution is equal to the difference in the value of C ∈ C caused by the addition of vi:

• (b) Node vi can join a disconnected coalition C ∈ ˜ C and the resulting coalition becomes connected, i.e., C ∪ {vi} ∈ C. Here, vi's contribution is the whole value of C∪{vi}: mci(C) = νf (C ∪ {vi}) - νf (C) = f (C ∪ {vi})
• (c) Node vi can join a connected coalition C ∈ ˜ C and the resulting coalition becomes disconnected, i.e., C ∪ {vi} ∈ ˜ C. This means that vi brings down the value of C to 0: mci(C) = νf (C ∪ {vi}) - νf (C) = -f (C)
• (d) Node vi can join a disconnected coalition C ∈ ˜
• C and the resulting coalition remains disconnected, i.e.,C∪{vi}∈ ˜ C: mci(C) = νf (C ∪ {vi}) - νf (Cı)) = 0

The key conclusion to be drawn from the above analysis is that both connected and disconnected coalitions play a role when computing the Shapley value. This is because a node can contribute not only to a connected coalition, but also to a disconnected one (by making it connected). However, in the further sections, we will show that it is possible to develop an exact algorithm that only cycles through connected coalitions.

GeneralSV Algorithm

Based on the observation that both connected and disconnected coalitions play a role when computing the SV, we construct the general-purpose Shapley value algorithm

Algorithm 1: GeneralSV Algorithm for the SV

Input: Graph G = (V, E) and characteristic function νf Output: Shapley Value, SVi(νf ), for each node vi ∈ V 1 foreach vi ∈ V do 2 SVi(νf) ← 0; 3 foreach C ∈ 2V do 4 CheckConnectedness(C); 5 if C ∈ C then 6 foreach vi ∈ N(C) do 7 SVi(νf ) ← SVi(νf ) + ξC (νf (C ∪ {vi}) - νf (C)) 8 foreach vi ̸∈ N(C) do 9 SVi(νf ) ← SVi(νf ) - ξCνf (C) 10 else 11 foreach vi ∈ N(C) do 12 CheckConnectedness(C ∪ {vi}) 13 if C ∪ {vi} ∈ C then 14 SVi(νf ) ← SVi(νf ) + ξCνf (C ∪ {vi})

(GeneralSV) for computing the SV in connectivity games defined by Amer and Gimenez. It is presented in Algorithm 1, where for each C ∈ 2V , we denote by N(C) the set of all neighbours of C. Essentially, for each coalition C ∈ 2V this algorithm considers cases (a), (b) and (c) as outlined in Figure 2 in our paper. 5 In all of these three cases, a node vi can make a non-zero contribution by joining a coalition. We note that function CheckConnectedness(C) runs in O(|C| + |E(C)|).

Unfortunately, the use of this algorithm in practice is limited by the number of nodes in the network. It runs in O((|V | + |E|)2|V | ) and already for |V | = 50, the Algorithm 1A has to cycle through more than 1015 coalitions. In our paper, we developed an algorithm that for many networks is able to compute the SV substantially faster.

FasterSVCG Algorithm

Many real-world terrorist networks are sparse, i.e., |C| ≪ | ˜ C| [Krebs, 2002]; thus, if the Shapley value could be computed only by considering coalitions in C, it would be possible to analyse much larger terrorist networks. To this end, for each vi ∈ V , let us define the following disjoint sets of coalitions:

which correspond to cases (a), (b) and (c) from the previous section. Based on this, the Shapley value can be computed as:

5 As for (d), it can be disregarded since the marginal contribution in this case equals 0.

where case (d), when mci(C) = 0, is simply omitted. The key idea behind our exact algorithm to compute the Shapley value in connectivity game (abbreviated FasterSVCG) is to represent the sets C+ i and Ci differently, such that ˜ C does not appear in the new representation. 6 In particular, we represent C+ i and Ci as follows, where P(C) is the set of agents that are pivotal to C, and N(C) is the set of neighbours of C:

Now since ˜ C no longer appears in the definitions of C# i , C+ i and Ci , it is possible to compute the Shapley value as in equation (8) without enumerating any of the coalitions in ˜ C. Based on this, our algorithm enumerates every connected coalition, C ∈ C, and determines for each agent vi ∈ C whether C \ {vi} ∈ C# i or C \ {vi} ∈ C+ i and for vi ̸∈ C if C ∈ Ci . 7 The enumeration is carried out using Moerkotte and Neumann [2006]'s method-the fastest such enumeration method in the literature. Its basic idea is that, for each connected coalition C ∈ C, it expands C by adding to it certain subsets of its neighbours. These subsets are chosen so as to ensure that no connected coalition is enumerated more than once (see Moerkotte an Neumann [2006] for more details).

Next, we explain our algorithm. To enhance clarity, for every connected coalition C ∈ C, we will define three disjoint sets of agents: V # C = {vi ∈ C : C\{vi} ∈ C# i }, V + C = {vi ∈ C : C \ {vi} ∈ C+ i }, and V - C = {vi ∈ V \ C : C ∈ Ci }. If we compute the above sets for every C ∈ C, then we can compute the Shapley value. Let us take a closer look at the difficulty of computing those sets for a given C.

• Computing V - C can be done in O(|V |) time. This is because the agents in V - C are basically all those that are not members, nor neighbours, of C.
• Now, to compute V + C , we need to find the pivotal agents in C. This can be computed using a method "findPivotals" that runs in O(|V | + |E|) [Alsuwaiyel, 1999].
• Having computed V + C , it becomes easy to compute V # C . This is because V # C = C \ V + C .

From the above analysis, it is clear that the main difficulty lies in findPivotals. Therefore, whenever possible, we would like to compute V + C using some other, easier, technique. In particular, when we expand a connected coalition, C, into another connected coalition C ′ = C ∪ S, we try to update the set of pivotal agents, rather than compute it from scratch with findPivotals. Here, we distinguish between three conditions:

• Condition 1: The cycles in C ′ are exactly like those in C. In this case, the set V + C′ consists of elements of V + C , expanded by the nodes in C that are connected to S.
• Condition 2: C ′ contains a cycle that is not in C. Here, we need to call findPivotals.

6 As for C# i , it does not depend on ˜ C, and so there is no need to represent it differently.

7 Note, that we do not consider the impact of agent vi ̸∈ C that do not disconnect C because the contribution of this agent will be calculated for connected coalition C ∪ {vi} as C ∈ C# i .

Algorithm 2: FasterSVCG for SVi(νf ), vi∈V

Input: Graph G=(V, E) and characteristic function νf Output: Shapley value SVi(νf ) of each node vi∈V 1 X ← V ;// initialize X, which is only used for Moerkotte & Neumann's enumeration 2 foreach vi ∈ V do SVi(νf) ← 0; 3 for i ← |V | to 1 do 4 computeSV ({vi}, N (vi), X, X \ (N (vi)∪{vi}), ∅); X ← X \ {vi} // ----------- Next, we define computeSV ----------- 5 computeSV (C,NC,X, V - C , V + C ) begin 6 X′ ←X ∪NC; // where NC consists of the neighbours of C 7 foreach S ⊆ (NC \ X) ∧ S ̸= ∅ do 8 C ′ ←C; // a new coalition that will be constructed from the old coalition C NC ′ ←NC \ S; // the neighbours of C′ 9 isCycle ← false;// to indicate whether a new cycle has appeared while constructing C′ 10 foreach v ∈ S do 11 TEMP ← ∅; // a temporary set used to compute neighbours of: C′ ∪ {v} TEMP2 ← ∅; // a temporary set used to compute the pivotal agents in: C′ ∪ {v} foreach u ∈ N (S) do 12 if u /∈ (C ∪NC) then 13 TEMP ← TEMP ∪ {u}; 14 else if (isCycle = false) ∧ (u ∈ C ′ ) then // condition 1 15 TEMP2 ← TEMP2 ∪ {u}; 16 if |TEMP2| > 1 then // condition 2 17 isCycle ← true; 18 C ′ ← C ′ ∪ {v}; NC ′ ← NC ′ ∪ TEMP; 19 V - C′ ← V - C′ \{v} \ TEMP; 20 if isCycle = false then // condition 1 21 V + C′ ← V + C′ \{v} ∪ TEMP2 ; 22 if |C′ | = 2 then // condition 3 23 V + C′ ← ∅; 24 else if isCycle = true then // condition 2 25 V + C′ ← F indP ivotals(C ′ ); 26 foreach vi ∈ C ′ do // update Shapley value 27 if vi ∈ V + C′ then 28 SVi(νf ) ← SVi(νf ) + ξC′ \{vi}f (C′ ) 29 else // deal with the set V # C′ 30 SVi(νf )← SVi(νf )+ξC′\{vi}(f (C′ )-f (C ′ \{vi})) 31 foreach vi ∈ V - C′ do // update Shapley value 32 SVi(νf ) ← SVi(νf ) - ξC′ f (C′ ) 33 computeSV (C′ , NC′ , X′ , V - C′ , V + C′ );

• Condition 3: |C| = 2. In this case, since we assumed that a singleton is a connected coalition, none of the two agents in C is pivotal.

The pseudocode of FasterSVCG is presented in Algorithm 1. It is easy to see that it runs in O((|V | + |E|)|C|).

In the next section we propose an approximation algorithm that is able to provide a ranking for larger networks.

ApproximateSVCG Algorithm

ApproximateSVCG is our dedicated application of Monte Carlo sampling to connectivity games. Unlike the existing algorithm to approximate the Shapley value for characteristic function games [Castro et al., 2009], in our algorithm we do not sample permutations, but coalitions. Since any marginal contribution of an agent, vi, links two coalitions-one with this agent, i.e., C ∪ {vi}, and one without him, i.e., Csampling of coalition C can be viewed as sampling of vi's marginal contribution. Generally speaking, in our algorithm, we will randomly select a number of marginal contributions of vi and approximate the SVi using the resulting average. Due to the fact that, in formula (4) for the Shapley value, marginal contributions are calculated with different weights, to obtain an unbiased estimator we have to sample marginal contributions with appropriate probabilities. To this end, we propose the following general process. In Step 1, we uniformly select k ∈ {0, . . . , |V |}. In Step 2, we choose a random coalition C of size k, 8 and in Step 3, for every agent, compute the marginal contribution of this agent obtained by leaving/entering C. To better understand our motivation, let us transform the formula for the Shapley value as follows:

From this formula it is clear that, to obtain an unbiased estimator, the sampling method should satisfy two conditions:

• (i) the probability that a randomly chosen marginal contribution is obtained from entering a coalition of size k is equal for every k: 1 n+1 · n-k n + 1 n+1 · k+1 n = 1n (n = |V |); 9
• (ii) marginal contributions to all coalitions of size k are chosen with the same probability.

This technique allows us to compute the marginal contributions of all agents for a randomly selected coalition, which in the connectivity games (and, potentially, in many more classes of games) can be performed much faster than estimating the Shapley value for each player separately [Mann and Shapley, 1962] or by sampling of a random permutation [Castro et al., 2009], where we have to calculate the marginal contributions for a sequence of coalitions growing in size.

8 To this end, we take the first k elements of a random permutation (generated uniformly with Knuth shuffle). This method is unbiased, as every coalition appears in the same k!(n - k)! number of permutations.

9 Note that a given marginal contribution appears twice in our process-the first term represents the probability that we select a coalition of size k without player vi, while the second one-that we select the corresponding coalition of size k + 1, with player vi.

Algorithm 3: ApproximateSVCG for SVi(νf ), vi∈V

Input: Graph G=(V, E) and characteristic function νf Output: Shapley value SVi(νf ) of each node vi ∈ V 1 foreach vi ∈ V do SVi(νf) ← 0; 2 for it = 1 to maxIter do 3 k ← random number from {0, . . . , |V |}; 4 C ← random coalition of size k; 5 if !CheckConnectedness(C) then continue; 6 P ←FindPivotals(C); 7 foreach vi ∈ C \ P do // case (a) 8 SVi(νf )←SVi(νf )+ |V |+1 |C| ·(f(C)-f(C\{vi})) 9 foreach vi ∈ P do // case (b) 10 SVi(νf )←SVi(νf ) + |V |+1 |C| · f(C) 11 foreach vi ∈ (V \ C) \N(C) do // case (c) 12 SVi(νf)←SVi(νf) - |V |+1 |V |-|C| · f(C) 13 foreach vi ∈ V do SVi(νf) ←SVi(νf)/maxIter;

To this end, in the ApproximateSVCG algorithm we merge our Monte Carlo technique with the analysis of marginal contribution presented before and used in FasterSVCG. The pseudo code is presented in Algorithm 2. Line 3 corresponds to Step 1, where we sample the size of a coalition. Now, we modify Step 2 in order to select only connected coalitions (lines 4 and 5). 10 We also modify Step 3, when we consider cases (a), (b), and (c) from Figure 2 (lines 7-12). The modification of Step 3 has to be done due to the following reason: since we no longer consider disconnected coalitions, any nonzero marginal contribution made to a disconnected coalition have to be transferred to a corresponding connected coalition (lines 8, 10, and 12). Furthermore, this should be done in a way that preserves appropriate probabilities (thus, in lines 8, 10, and 12 we multiply marginal contributions by adequate weights). Finally, we divide the sum of the contributions by the number of iterations (lines 13). For every sample, algorithm runs in time O(|V | + |E|).

10 It should be noted, that generating a random connected coalition uniformly will create a biased algorithm.

4 Performance Evaluation

We generate random graphs focusing on two topologies commonly found in social networks, and in terrorist organisations in particular [Krebs, 2002; Sageman, 2004]: (i) scale-free graphs (SFGs), where the network is generated according to a power law; and (ii) random trees (TG), which model hierarchical organisations. To construct SFGs, we use the preferential attachment generation model [Albert and Barab´asi, 2002], with parameters k = 1, 2, 3 (cfr. [Voice et al., 2012]). 11 To construct TGs, every new node is attached to a randomly picked incumbent. Finally, we include in our analysis (iii) complete graphs, where all coalitions are connected. Although complete graphs are unlikely to arise in a terrorist network context, they constitute a suitable benchmark for our simulations. For all the games on random graphs we assume that f is defined as in (2).

FasterSVCG: In Figure 3(a), we compare the performance of FasterSVCG to the general-purpose Shapley value algorithm (abbreviated GeneralSV). 12 Clearly, this latter algorithm runtime is the same for any type of graph. Unlike GeneralSV, FasterSVCG takes advantage of the sparsity of the network and, consequently, significantly outperforms the benchmark. For instance, for SFG(k = 2) and |V | = 30, FasterSVCG needs only 0.39% of GeneralSV runtime! Naturally, the best performance is obtained for TGs, where the game over a network of 30 nodes can be computed in about 3 seconds.

ApproximateSVCG: In Figure 3(b), we evaluate the time performance of ApproximateSVCG. Importantly, for our purpose of identifying key terrorists, we are mostly interested in the approximation of the correct (Shapley value) ranking of top nodes, and less in the approximation of their actual Shapley values. To this end, we evaluate the time required by ApproximateSVCG to obtain the ranking of the top ⌈√n⌉ nodes, with at most one error (i.e., one inversion compared to the exact ranking). We present an average time calculated over 500

11 In this model, while gradually constructing a graph, every new node vi is linked to k incumbents such that the probability that vi is linked to incumbent vj is degree(vi) ∑j degree(vj) .

12 All experiments are carried out on a 64 bit, Intell Zeon E5-2643 with 2 CPU (8 cores each) 3.3 Ghz, 128GB RAM. For |V | ≤ 25, we repeated each experimental run 50, for 26 ≤ |V | ≤ 30-30 times. In the experiments involving random graphs no parallel computations were performed. Krebs' 9/11 network was analyzed with a parallelised code on 16 cores (each individual core was assigned with computing a tree for one node).

iterations, each for a randomly selected SFG(k = 4), with 75% confidence level. ApproximateSVCG returns top nodes much faster than FasterSVCG-for the graph of 24 nodes the former algorithm runs in 0.25 sec. and the exact one in 72 sec.

As far as other than ⌈√n⌉ thresholds are concerned, the lower the threshold, the faster our Monte Carlo method becomes (and vice versa). Also ApproximateSVCG becomes faster, the higher the allowable error is (measured with the number of allowable inversions). Finally, we note that ApproximateSVCG is faster than our exact algorithm in generating an error-free rankings (on average, approximately 6, 26, and 174 times faster for 15, 20, and 25 agents, respectively).

Figure 4 presents the error convergence of the ApproximateSVCG and compares the results to the random permutation sampling studied by Castro et al. [2009]. Here, we focus on the maximum absolute error of the Shapley value, computed as a percentage of the value of the grand coalition. The results are calculated for Krebs' 9/11 WTC terrorist network with 36 nodes (as an average from over 30 iterations). ApproximateSVCG outperforms Castro's method-after 4 second, the error of ApproximateSVCG equals 0.029%, while for Castro et al. exceeds 0.2%. The fact that the absolute error ultimately converges to zero indicated that our sampling method is not biased.

New insight on Krebs' 9/11 WTC network: In the already classic work, Krebs [2002] constructed the 9/11 network from publicly available sources and computed standard centrality metrics to determine the key players in this network. Lindelauf et al. instead used their new centrality metric and, similarly to the case of the Jemaah Islamiyah's network, argued that the Shapley value-based approach delivers qualitatively better insights (as it captures the network structure in a more sophisticated manner). However, Lindelauf et al.'s analysis focuses only on the network of 19 hijackers with 32 relationships, whereas Krebs reported also a bigger network of 36 nodes and 125 edges (mentioned above) that included accomplices. With FasterSVCG, we were able to analyse this bigger network as well. The computations took 38 minutes during which FasterSVCG traversed 401.963.129 connected coalitions (0.59% of all).

Interestingly, the five top terrorists (out of 36) identified by FasterSVCG differ from the top five terrorists reported by Lindelauf et al. when only the network of 19 terrorist was taken into account-see Table 1. One of the differences is with respect to M. Atta, who was widely believed to be one of the ring-leaders of the conspiracy [Krebs, 2002] and was positioned the third place in our computations, but was classified in Lindelauf et al.'s work on the 6th place.

5 RelatedWork

A rapidly growing body of work is directed to the analysis of terrorist organisations using the methods of social network analysis. A very good introduction to this line of research can be found in Ressler [2006]. Also worthy of note is the work of Farley [2003], Carley [2003], and Husslage et al. [2012], who conduct quantitative analysis of the terrorist networks.

Since the work of Grofman and Owen [1982], a number of game-theoretic centrality measures have been developed either to enrich the existing well-known centralities or as completely new ones (e.g., [Van den Brink et al., 2007; G´omez et al., 2003; Szczepa´nski et al., 2012]). In the terrorist network context, Lindelauf et al. [2009a; 2009b] employed the game-theoretic approach to analyze covert networks.

In the first computational analysis of game-theoretic centrality, Aadithya et al. [2010] present polynomial time algorithms for computing Shapley value-based centrality measures built upon four coalitional games that modelled possible influence of coalitions on their neighbours. In subsequent work, Szczepanski et al. [2012] presented an algorithm for the Shapley value-based betweenness centrality.

We also mention works on the Shaple value approximation algorithms ([Fatima et al., 2007; Bachrach et al., 2008a]).

The hardness result presented in this paper is consistent with other studies of the complexity of the Shapley value in various settings. For instance, computing the Shapley value was shown to be #P-Complete for weighted majority games [Deng and Papadimitriou, 1994] and in minimum spanning tree games [Nagamochi et al., 1997]. Aziz et al. 2009 obtained negative results for a related problem of computing the Shapley-Shubik power index for the spanning connectivity games that are based on undirected, unweighted multigraphs. Also, Bachrach et al. [Bachrach et al., 2008b] showed that the computation of the Banzhaf index for connectivity games, in which agents own vertices and control adjacent edges and aim to become connected to the certain set of primary edges, is #P-Complete. A comprehensive review of these issues, including some positive results for certain settings, can be found in [Chalkiadakis et al., 2011].

6 Conclusions

In this paper, we proposed an algorithm to compute the Shapley value for the connectivity games of Amer and Gimenez defined over arbitrary graphs. Although our method is general, it has been created with an aim to study centrality metrics proposed by Lindelauf et al. to identify key individuals in terrorist networks. We proved that the problem is #P-Hard. Nevertheless, using our exact algorithm we were able to analyse in moderate time the 36 node version of the network responsible for the 9/11 WTC terrorist attacks. We also presented the approximate algorithm that allows for an efficient study of bigger networks and for further validation of the Lindelauf et al's metrics.

Acknowledgments

We would like to thank the anonymous IJCAI reviewers for valuable feedback. Tomasz Michalak and Michael Wooldridge were supported by the European Research Council under Advanced Grant 291528 ("RACE"). Talal Rahwan and Nicholas R. Jennings were supported by the ORCHID Project, funded by EPSRC (Engineering and Physical Research Council) under the grant EP/I011587/1.