Mining heterogeneous terrorist attack network using personalized PageRank

Abstract

Majority of the studies on counter-terrorism using social network analysis consider homogeneous networks built over either terrorists or terrorist organizations. However, terrorist attacks are often defined using heterogeneous attributes such as location, time, target type, organization, etc. This paper constructs a heterogeneous terrorist attack network considering heterogeneous attributes and captures heterogeneous influences propagated from different attributes using Personalized PageRank. Personalized PageRank is a flexible model capable of propagating supervised information while traversing over a network using different personalized parameters. This study investigates effects of various parametric setups to study influence of various factors such as news media discussions, historical activities, temporal behavior etc., on one of the important counter-terrorism problems; prediction of future attacks of a terrorist organization. From various experimental observations, it is evident that news media discussion and network’s temporal behavior have a positive influence on future activities of a terrorist organization. Further, this paper investigates responses of various node proximity based link prediction methods on predicting future relationships between a terrorist organization with other attributes (such as country, city and target types). Majority of the studies on link prediction using node proximity ignore node importance. However, in a heterogeneous environment, nodes from different classes may have different importance. This paper proposes new variants of four proximity based link prediction methods, namely, Adamic Adar, Jaccard Coefficient, Resource Allocation, and Common Neighbor, which have the capability to incorporate node importance. With suitable experiments, we show that the proposed variants of link predictors are more accurate at predicting relations than their state of art counterparts.

Keywords

Heterogeneous network social network analysis counter-terrorism personalized PageRank external information

1. Introduction

With the increase in relevance of applying complex network analysis solutions for addressing real world problems, a spur in applying social network analysis (SNA) techniques in counter-terrorism and homeland security has been witnessed in recent time [19,36,37]. SNA solutions to the problems such as node centrality, edge betweenness, node influence, community detection etc., have direct relevance to the intelligence questions such as (i) identification of criminal or the communication channel so that elimination of which will result in organization break down, (ii) determining hidden relationships between activists and terrorist organizations, (iii) systematic evolution of community, etc. Although analogy between intelligence/counter-terrorism problems and the social network analysis problems is established long before $9 / 11$ attack, SNA methods have not been used effectively in counter-terrorism domain. After the $9 / 11$ attack, many intelligence researchers have visibly started exploiting SNA methods and tools for counter-terrorism activities [19,35].

Majority of the earlier works on SNA for counter-terrorism have mainly exploited homogeneous networks (network with only one class of nodes and one class of ties). For example, network of terrorists have been used to study $9 / 11$ and $3 / 11$ attacks in [19] and [36] respectively. These studies focus on mining only the homogeneous structural properties of a network. However, characteristics of the real world terrorist attack data may be heterogeneous in nature. For example, terrorist organizations may be related through similar target types, place of attack or organizational ideology. Therefore, there is a need for methodologies which are capable of exploiting heterogeneous characteristics of the network such as heterogeneous relationships, heterogeneous node types etc. This is the main motivation of this study. In this paper, we extend our earlier work [2] for predicting relationships between heterogeneous attributes over a terrorist attack network.

An event of terrorist attack is defined by various attributes such as date and time of attack, place of attack, type of attack, target type, weapon used, terrorist organization involved etc. [31]. This paper considers similar attributes and constructs heterogeneous attack network using Global Terrorism Database (GTD1

¹
https://www.start.umd.edu/gtd

). Over this network, the study reported in this paper focuses around two conceptual perspectives; (i) node centrality estimation in a heterogeneous environment, and (ii) link prediction between different attributes. Unlike a homogeneous network, heterogeneous networks have potential to capture relationships by considering different scenarios. For example, estimating centrality of nodes by considering higher importance to a subset of node types than others, or influence of different node type/relation type on tasks such as centrality measure or link prediction, etc. Therefore, there is a need for parametric solutions which can potentially exploit various scenarios without changing the underlying framework. Motivated by this concept, in this paper we revisit Personalized PageRank (PPR) [12] (a random walk based centrality measure) and investigate PPR as a parametric approach capable of capturing different scenarios for estimating node centrality.

Several link prediction methods have been proposed in the literature, e.g. proximity based [21], path based [21], tie weight based [29,38], random walk based [24] etc. Except for few random walk based approaches, a majority of the methods do not consider node importance while predicting future relations. However, in the context of heterogeneous network (terrorist attack network in particular), node importance may play an important role. For instance, a terrorist organization may prefer to attack a country which is popular across the globe to achieve more attention. To capture the node importance, this paper further re-formulates the existing proximity based link prediction methods and investigates the effects.

For understanding the structural changes of a network, information diffusion plays an important role. From papers [29] and [3], it is observed that information propagation in a network is susceptible to exogenous information too, such as, news and social media, structural changes over time, etc. Moreover, external sources such as, news and social media play an important role in populating ideology, motivations and hate messages of terrorist organizations [15,30,34]. Therefore, there is a need for incorporating effects of external information for mining the terrorist attack network. As stated above, PPR can be used as a single model which is capable of incorporating different scenarios (for details refer Section 3.2). Therefore, we exploit PPR to capture the effects of two types of external information sources, namely, (i) news media, and (ii) temporal dynamics of underlying network on estimating the node centrality. The centrality score thus obtained from PPR is further used as node importance by reformulating common neighbor (CN), Jaccard Coefficient (JC) [14], Adamic Adar (AA) [1] and resource allocation (RA) [49]. We observe that incorporating temporal dynamics improves the performance of predicting relations between heterogeneous attributes such as, terrorist group to country, city, targets, etc. However, news media discussion helps in predicting relations between the terrorist organizations.

We summarize main contributions of this paper as follows:

Projecting personalized PageRank as a potential solution to capture various heterogeneous scenarios (without changing underlying model) while estimating network centrality.

Projecting personalized PageRank as a potential framework to seamlessly incorporate information from external sources.

Reformulating existing proximity based link prediction methods to incorporate node weight.

Predicting relationship between heterogeneous attributes of the network.

Rest of the paper is organized as: Section 2 discusses existing studies on SNA in counter-terrorism, the relation between media and terrorism, link prediction and centrality measures in heterogeneous information network. We present proposed framework in Section 3 which gives the detailed reformulation strategies of PPR and proximity-based link prediction methods. This is followed by dataset and experimental setups in Section 4 while experimental observation and discussion is given in Section 5. Section 6 concludes the paper with presenting future possibilities.

2. Related study

This section reviews four aspects of studies related to this paper, namely, (i) SNA for counter-terrorism, (ii) Media and Terrorism, (iii) Link prediction on Heterogeneous Information Network (HIN), and (iv) Centrality measures in HIN.

2.1. SNA for counter-terrorism

Social Network Analysis was exploited by Sparrow [40] for the first time to identify terrorists/criminals that need to be neutralized for destabilizing the network of conspirators. Though this study has demonstrated the strength of using SNA techniques in counter terrorism prior to $9 / 11$ attack, a majority of studies on terrorism and counter-terrorism prior to the attack have not exploited SNA techniques to a larger extent. However, post $9 / 11$ attack sudden burst in using SNA techniques in counter-terrorism study is evident. In the study [19], author maps nineteen terrorists involved in $9 / 11$ attack using different centrality measures on a network constructed using different social relations such as kinship, siblings, schooling etc. In a similar study [36], author studies a terrorist network to identify conspirators of $3 / 11$ attack by exploiting different centrality measures. From the papers [19,36], and [37], it is observed that SNA can be a useful methodology in predicting terrorist attacks in advance and understanding various phenomena such as organizational structure, economic transactions, voting patterns by identifying relationship between different conspirators (terrorist, financier, etc.) and analyzing their importance. However, all of the above studies consider data related to a particular terrorist attack which is small and homogeneous in nature. As discussed above a terrorist attack can be defined more clearly in terms of a heterogeneous network, this paper constructs a heterogeneous terrorist attack network over global terrorist attack data and attempts to address two SNA problems, namely, centrality and link prediction.

2.2. Media and terrorism

In recent era, terrorism has evolved to a new level which may be visualized as a consequence of the availability of various easy to communicate media, such as, News, Internet, and Social Media. Availability of such platforms enable terrorist organizations to perform various activities such as recruitment, finding sympathizers, populating propaganda, arranging campaigns etc. [15,30].

Mutual dependency or symbiotic relationship between news media and terrorism is widely visible. Media industries are often attracted by the sensational and trending news created by terrorist organizations and the reporting acts as free publicity for terrorists [34]. According to the study [26], huge news media reporting may sometimes result as an Enabler of Act of Terrorism. At the same time, media attention towards an attack often depends on the modus operandi of the attack, geographical importance and political orientation [16].

2.3. Link prediction in Heterogeneous Information Network (HIN)

Link prediction in HIN is an important problem and has got much popularity in recent past [39]. However, there is no study exploiting a HIN for answering questions related to counter-terrorism, such as, (i.) which terrorist organization can be the major threat to a country in future, (ii.) which city can be the target city by a terrorist organization in future, (iii.) which target types can be attacked by a terrorist group in future, etc. Existing studies related to link prediction over HIN can broadly be grouped into two approaches; (i) meta path based models [5,6,41,42,48], and (ii) probabilistic models [7,46,47]. Link prediction algorithms that exploit meta paths generally consider two-step process. In the first step, meta path based feature vectors are extracted, and the second step employs a machine learning model (such as regression, classification, etc.) to determine the existence of links. For instance, in study [41], a model named PathPredict is proposed to solve the problem of co-authorship relationship prediction, which uses various features generated using meta paths and a logistic regression based prediction model.

Probabilistic modeling for link prediction in HIN has also been well explored. The study [46] proposes an influence propagation based link prediction method by exploiting conditional probability in a multi-relational network. In a similar approach, the paper [47] proposes a topical factor graph model to aggregate information from different heterogeneous data sources and designs a semi-supervised learning model to find relationships. Further, the study [7] proposes a transfer-based ranking factor graph model which combines different social patterns to predict links in a network.

Unlike above studies which focus on tie weight, this paper focuses on node importance while formulating link prediction methods.

2.4. Centrality measures in HIN

Centrality measures have been used in many aspects of network mining problems [4,13,18]. Like link prediction, several studies have also proposed centrality measures for HIN by considering meta paths [20,25]. For example, Liu et al. [25] propose a ranking framework for publications with pseudo-relevance feedback by exploiting several meta-paths in a heterogeneous bibliographic network. Further, Li et al. [20] propose HRank to rank objects and meta-paths simultaneously in HIN. However, all of these works are limited to incorporating the topological structures (in the form of meta-path).

Tsai et al. [44] propose SocialRank which uses external information like social hints for image search and ranking in social networks. In a similar direction, this paper also exploits external information such as news media and temporal dynamics of the network, and rank the nodes using Personalized PageRank (PPR).

3. Proposed framework

This section elaborates the proposed framework in details. As defined in Section 1, a terrorist attack can be defined by many attributes. In this study, we construct HIN of terrorist attacks by connecting various attributes defining the attacks (refer Section 4 for details).

Fig. 1.

Heterogeneous network with three types of weighted node and link classes, size of nodes and thickness of links show their importance.

3.1. Heterogeneous Information Network (HIN)

A heterogeneous information network can be represented as $G = (V, E, V, E)$ , where V is the set of nodes, E is the set of edges, $V$ is the set of node classes, and $E$ is the set of edge classes. Every node in V belongs to one of the class label in $V$ and every edge in E belongs to one of the classes in $E$ . Further, the nodes and edges in the network may be associated with some weights representing their importance. Thus, a weighted heterogeneous information network can be formally defined as follows.

Definition 1 (Weighted HIN).

It is defined by a six tuple $G = ⟨ V, E, V, E, ω_{v}, ω_{e} ⟩$ , where $ω_{v}$ and $ω_{e}$ denotes the vectors defining node weights and link weights respectively. The node weights may be defined using network specific domain information such as class importance, centrality of the nodes in the network etc. Similarly, edge weights may be defined by relation specific information such as frequency of occurrences, communication between the nodes etc. (refer Fig. 1 for a sample heterogeneous terrorist attack network).

If $ω_{v} (x) = ω_{v} (y)$ , $\forall x, y \in V$ and $ω_{e} (i) = ω_{e} (j)$ , $\forall i, j \in E$ , then weighted graph G is same as unweighted graph G. Further, if $ω_{v} (x) = 0$ , $\forall x \in V_{i}$ , then it is equivalent to removing node type $i \in V$ from the graph. Similarly, $ω_{e} (j) = 0$ , $\forall j \in E_{i}$ to remove link type i from the graph. Thus, we can realize a homogeneous graph as a special case of a heterogeneous graph i.e., $ω_{v} (x)$ and $ω_{e} (j)$ are non-zero only for one class.

3.2. Node importance and centrality measures

Ranking of nodes may contribute to the relationships they form with other attributes. Particularly in case of a terrorist attack network, the likelihood of forming a relationship between a high influence terrorist organization and target type of high reputation may be more. It is quite intuitive that attacking a target type of high repute would serve the motives of a terrorist way faster. Considering this motivation we incorporate the node importance to predict the relationships between different nodes.

Several centrality measures have been proposed in literature i.e. degree [9], betweenness [23], closeness [9], PageRank [4], Eigenvector [17] etc. As this study aims at incorporating the effects of external information on a heterogeneous terrorist attack network, we chose Personalized PageRank (PPR) as a method capable of incorporating external information as its personalization parameter.

For counter-terrorism, frequently appearing attributes defining a terrorist attack may be of more importance. To incorporate this intuition, we also propose Total Frequency and Recent Frequency of appearance (refer Section 4.1) by the nodes as personalization parameter for the proposed heterogeneous terrorist attack network.

3.2.1. Random walk based method

Given a Markov transition matrix A of a network G, let $x^{t}$ be a vector such that $x^{t} [i]$ denotes the probability that a random walker is at the node $i \in V$ after time t. Now, $x^{t}$ can be defined as below [33]. $\begin{matrix} x^{t} [i] = \sum_{j \in V} x^{t - 1} [j] A [j, i] \end{matrix}$ Considering for all the vertices in the network, the above expression can be written as $\begin{matrix} x^{t} = A x^{t - 1} \end{matrix}$ If the random walker infinitely keeps walking, it may converge to final stationary distribution vector x i.e., $\begin{matrix} x = A x \end{matrix}$ If the matrix A is stochastic and primitive, x converges to principle eigenvector whose principle eigenvalue is 1. Now, a real network such as Web hyperlink, social network, biological network may not be primitive. Brin and Page in their seminal paper [4] address this problem by introducing a damping factor d which allows the random walker to stop the walk and restarts from a random node, and propose the popular PageRank centrality measure. Thus, the PageRank of a node $i \in V$ is defined as below. $\begin{matrix} x [i] = d \sum_{j \in V} x [j] A [j, i] + (1 - d) \frac{1}{n} \end{matrix}$ where n is the number of node in the network and the damping factor d is the probability of continuing random walk by following the links in the network and $(1 - d)$ is the probability of jumping to a random node. In other words, we can write it as below. $\begin{matrix} (1) & x = [d A + (1 - d) I v^{T}] x \end{matrix}$ where I is the identity vector i.e., $I^{T} = {1, 1, 1, \dots, 1}$ and $v^{T} = {\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n}}$ . By adding the second term, the transition matrix $d A + (1 - d) I v^{T}$ is primitive.

In the above PageRank formulation, a random walker jumps to any random node with equal probability i.e., $\frac{1}{n}$ . However, in a heterogeneous network, different classes of nodes may have different privileges. We may wish to determine centrality of a network or similarity between nodes by considering certain classes of the node with higher importance. Thus, we have adopted Personalised PageRank to address the problem of centrality in a heterogeneous network.

3.2.2. Personalised PageRank for heterogeneous network

Unlike PageRank, personalised PageRank assumes that different user will have a different walking preference. A person in the film industry may prefer to visit web pages in entertainment domain more than literature. In such a scenario, traditional PageRank fails to capture user’s preferences. Personalized PageRank, as discussed in [10,12], incorporates user’s preferences and is defined as follows. $\begin{matrix} (2) & x = [d A + (1 - d) I p^{T}] x \end{matrix}$ where p is a stochastic personalized vector reflecting user’s preference of visiting the nodes in random jump i.e., $p [i]$ is the probability of jumping to node i by the user.

Table 1
GTD used for constructing heterogeneous terrorist attack network

ID Country Region Province City Attack type Target type Target subtype Group Weapon type Weapon subtype

1 India South Asia Assam Dibrugarh Bombing Educational Institution School/University ULFA Explosives Grenade

2 India South Asia Orissa Jajpur Bombing Transportation Bridge/Car Tunnel CPI-Maoist Explosive Land Mine

3 India South Asia Assam Kokrajhar Facility Transportation Train/Train Tracks NDFB Sabotage Equipment

4 India South Asia J&K Bijbehara Bombing Police Police Patrol LeT Explosives Vehicle

5 Nigeria Sub-Saharan Africa Borno Maiduguri Facility Religious Figures Place of Worship Boko Haram Incendiary Arson/Fire

6 Afghanistan South Asia Kandahar Kandahar Bombing Religious Figures Place of Worship Taliban Explosives Suicide

ID	Country	Region	Province	City	Attack type	Target type	Target subtype	Group	Weapon type	Weapon subtype
1	India	South Asia	Assam	Dibrugarh	Bombing	Educational Institution	School/University	ULFA	Explosives	Grenade
2	India	South Asia	Orissa	Jajpur	Bombing	Transportation	Bridge/Car Tunnel	CPI-Maoist	Explosive	Land Mine
3	India	South Asia	Assam	Kokrajhar	Facility	Transportation	Train/Train Tracks	NDFB	Sabotage	Equipment
4	India	South Asia	J&K	Bijbehara	Bombing	Police	Police Patrol	LeT	Explosives	Vehicle
5	Nigeria	Sub-Saharan Africa	Borno	Maiduguri	Facility	Religious Figures	Place of Worship	Boko Haram	Incendiary	Arson/Fire
6	Afghanistan	South Asia	Kandahar	Kandahar	Bombing	Religious Figures	Place of Worship	Taliban	Explosives	Suicide

Let B be the weighted adjacency matrix of the heterogeneous graph G. In general, matrix B may not be stochastic. We then perform the following transformation to make it a stochastic transition matrix. $\begin{matrix} B [i, j] = \{\begin{matrix} \frac{ω_{e} (i, j)}{\sum_{k \in V} ω_{e} (i, k)}, & if \sum_{k \in V} ω_{e} (i, k) \neq 0 \\ \frac{1}{| V |}, & otherwise \end{matrix} \end{matrix}$ Now, let q be a personalized stochastic vector representing the node priorities as defined by $ω_{v}$ of G i.e., $q [i] = \frac{1 + ω_{v} [i]}{\sum_{k \in V} ω_{v} [k] + | V |}$ . We provide smoothing parameter to avoid zero probability. Thus, we formulate personalized PageRank centrality for a heterogeneous graph by substituting A by matrix B and p by q in equation 2. $\begin{matrix} (3) & x = [d B + (1 - d) I q^{T}] x \end{matrix}$

Proposition 1.

The matrix $d B + (1 - d) I q^{T}$ in the equation 3 is stochastic and primitive.

Proof.

Since q is a stochastic matrix with non-zero elements, the matrix $I q^{T}$ is a stochastic matrix with non-zero elements. It has no zero elements i.e., it represents a completely connected graph. Therefore, $I q^{T}$ is irreducible and aperiodic. Further, the matrix B is stochastic by its construct. Since convex summation of two stochastic matrices is a stochastic matrix, the matrix $d B + (1 - d) I q^{T}$ is a stochastic matrix. Further, since $I q^{T}$ is irreducible and aperiodic, the convex sum is also a irreducible and aperiodic matrix. Hence, the matrix $d B + (1 - d) I q^{T}$ is stochastic and primitive. □

Without loss of generality, we can realize that the centrality vector x in equation 3 will converge to unique principle eigenvector of $d B + (1 - d) I q^{T}$ whose eigenvalue is 1. We use the centrality score of equation 3 to define estimate of $w_{v} (x)$ for the node proximity based link prediction estimates defined in Table 1.

3.2.3. Incorporating additional information

As mentioned in the earlier discussion, apart from the topological information, we extend our study with other information such as appearance in news publications, temporal characteristics of network entities. Such information may be available in terms of a vector or a matrix. The proposed PPR has the capability to incorporate such information without any problem. If the information is available in the form of a node vector r, equation 3 can be extended as $\begin{matrix} (4) & x = [d_{1} B + d_{2} I q^{T} + d_{3} I r^{T}] x \end{matrix}$ where $d_{1} + d_{2} + d_{3} = 1$ . Similarly, if the information is available in the form of a matrix R, equation 3 can be extended as $\begin{matrix} (5) & x = [d_{1} B + d_{2} {I q}^{T} + d_{3} R] x \end{matrix}$ Thus, the expression can be further extended if additional information is available from multiple sources.

3.3. Link prediction

Link prediction problem has a long history, which has been explored in several ways [22,28]. Given a network graph, the task of link prediction has been studied from various perspectives; (i) prediction of existing links, but yet unknown [1], (ii) prediction of non-existing links, but likely to appear in future [21], and (iii) prediction the life span of existing links (particularly in temporal and dynamic networks) [45]. In the past, researchers have proposed various unsupervised and supervised methods to address link prediction methods. Among the unsupervised approaches, existing methods include (i) local node proximity based methods [21], (ii) global path based methods [21], (iii) latent methods using matrix factorization [27] and (iv) random walk based methods [24]. On the other hand, authors have investigated the effect of various classification frameworks on link prediction by exploiting various features in the studies [43]. All of these studies consider homogeneous network. However, many of the real networks available today such as social networks, co-authorship networks, terrorism-related networks etc. are heterogeneous networks, where the network may have different types of nodes and links. Considering the heterogeneous nature of the networks, there is a need to adapt the existing methods or propose new methods suitable for heterogeneous networks. This paper focuses on adapting and reformulating existing methods (local node proximity based methods in particular) and study their effects on the heterogeneous network for link prediction.

Local Node Proximity Based Methods.
Given a weighted heterogeneous network G as defined in Definition 1, let $n (x)$ denotes the set of neighbor nodes (of any types) of the node x connected using any link type, and $n_{c}^{l} (x)$ denotes the set of neighbor nodes of type $c \in V$ of the node x connected using only link type l. Then, we adopt the traditional local node proximity based methods to heterogeneous networks as formulated below:
Common Neighbor (CN): The common neighbor score between two nodes x and y in homogeneous network is defined by the number of common nodes directly incident to the nodes x and y i.e., $S (x, y) = | n (x) \cap n (y) |$ . In heterogeneous network, the common neighbor score between two heterogeneous nodes x and y is defined as follows. $\begin{matrix} S (x, y) = \sum_{c \in V} \sum_{l \in E} \sum_{z \in n_{c}^{l} (x) \cap n_{c}^{l} (y)} ω_{v} (z) \end{matrix}$ With this scoring function, homogeneous CN becomes a special case of heterogeneous CN i.e., considering only one type of nodes and one type of links. For a homogeneous setup of node type c and link type l, the homogeneous CN score between homogeneous nodes x and y i.e., $S_{c}^{l} (x, y)$ can be obtained by assigning (i) zeros to all the entries of the node weight vectors and link weight vectors except for the nodes of type c and the links of type l, and (ii) 1 for nodes of type c and the links of type l.

Jaccard Coefficient (JC): For homogeneous network, traditional JC [14] between two nodes x and y is defined by $S (x, y) = \frac{| n (x) \cap n (y) |}{| n (x) \cup n (y) |}$ . In this paper, JC for heterogeneous network is defined as follows. $\begin{matrix} S (x, y) = \sum_{c \in V} \sum_{l \in E} \frac{\sum_{z \in n_{c}^{l} (x) \cap n_{c}^{l} (y)} ω_{v} (z)}{\sum_{z \in n_{c}^{l} (x) \cup n_{c}^{l} (y)} ω_{v} (z)} \end{matrix}$ Like CN, homogeneous JC is a special case of this heterogeneous estimate for the same conditions used for CN.

Adamic Adar (AA): Traditional AA index [1] between two nodes x and y for homogeneous network is defined as $\begin{matrix} S (x, y) = \sum_{z \in n (x) \cap n (y)} \frac{1}{log (| n (z) |)} . \end{matrix}$ If $d_{c}^{l} (z) = \sum_{i \in n_{c}^{l} (z)} w_{v} (i)$ i.e., sum of the node weights of c type neighbor nodes of z connected by link type l. We defined the heterogeneous counterpart as follows. $\begin{matrix} S (x, y) = \sum_{c \in V} \sum_{l \in E} \sum_{z \in n_{c}^{l} (x) \cap n_{c}^{l} (y)} \frac{w_{v} (z)}{log (1 + d_{c}^{l} (z))} \end{matrix}$ The 1 in the denominator is the regularization parameter to avoid division by zero. Like CN and JC, homogeneous AA estimate is also a special case of the heterogeneous AA.

Resource Allocation (RA): In [49], RA index between two nodes x and y for homogeneous network is defined as $\begin{matrix} S (x, y) = \sum_{z \in n (x) \cap n (y)} \frac{1}{| n (z) |} . \end{matrix}$ We then define the heterogeneous counterpart as follows. $\begin{matrix} S (x, y) = \sum_{c \in V} \sum_{l \in E} \sum_{z \in n_{c}^{l} (x) \cap n_{c}^{l} (y)} \frac{w_{v} (z)}{d_{c}^{l} (z)} \end{matrix}$ Like CN, JC, and AA, homogeneous RA is also a special case of heterogeneous RA.

4. Dataset and experimental setup

This study uses Global Terrorist Data (GTD) collected from National Consortium for the Study of Terrorism and Responses to Terrorism [31]. Each terrorist attack is defined by approximately hundred number of features. Out of these features, this study considers ten features which can potentially define an attack event; country, region, provincial state, city, attack type, target type, target subtype, terrorist organization, weapon type, and weapon subtype. These ten features represent ten different node classes in the experimental heterogeneous network. Table 1 illustrates a sample of experimental dataset extracted from GTD.

Based on Definition 1 and the dataset described in Table 1, the experimental heterogeneous network $G = ⟨ V, E, V, E, ω_{v}, ω_{e} ⟩$ is constructed in the following manner :

Node: The node set V is defined by unique set of feature instances from all the ten node classes discussed above. For example in Table 1 all the field values are treated as a node.

Edge Classes: Since the dataset consists ten classes of nodes, for an undirected network there can be $^{10} C_{2} = 45$ classes of edges ( $E$ ). Unlike earlier studies which consider few types of edges this work considers every possible edge types. This choice is based on the intuition that every relation between the various node classes collectively defines a terrorist attack event.

Edge: The edge set E is obtained by putting an edge between all the nodes which belong to same terrorist attack event. For example, the GTD network constructed using Table 1 will have edges between India and rest of the node class value available in the first four rows.

The vector

ω_{v}

is used to demonstrate the node importance which can be set by various centrality measures. However, in this study, all the nodes in GTD network are treated equally and

ω_{v}

is set to

I^{T} = {1, 1, 1, \dots, 1}

. Further

ω_{e}

is used as a vector containing edge importance. In this study, we measure the edge importance by the frequency of their appearance. Hence,

ω_{e}

contains the frequency of all the edges. For evaluation, we have considered the dataset between 2000 to 2009 as the training and 2010 to 2014 as the test dataset. Table 2 shows the characteristics of the datasets. Table 3 provides the count for different types of nodes used for training in this study.

Table 2
Characteristics of dataset and external information

Node Edge Duration

GTD Training 7177 92858 2000–2009

Test(gp-cn) 258 231 2010–2014

Test(gp-cty) 758 740 2010–2014

Test(gp-tar) 179 522 2010–2014

THE HINDU Training 7177 9699 2000–2009

Tensor GTD matrix Training 7177 92858 2000–2009

Tensor activeness vector Training 7177 NA 2000–2009

		Node	Edge	Duration
GTD	Training	7177	92858	2000–2009
Test(gp-cn)	258	231	2010–2014
Test(gp-cty)	758	740	2010–2014
Test(gp-tar)	179	522	2010–2014
THE HINDU	Training	7177	9699	2000–2009
Tensor GTD matrix	Training	7177	92858	2000–2009
Tensor activeness vector	Training	7177	NA	2000–2009

Table 3

Number of nodes in different classes for training data, TarType: target type, TarSubtype: target subtype, WeapType: weapon type, WeapSubtype: weapon sub type, and AttType: attack type

Country	Group	City	Region	Province
126	707	4751	12	1411

TarType	TarSubtype	WeapType	WeapSubtype	AttType
20	106	9	27	8

As reported in Section 2.2, external information such as news media, television, etc., share a symbiotic relationship with terrorist activities. Co-occurrence of different attributes defining a terrorist attack in news articles justifies the existence of relational dependencies among them. Therefore, to investigate the effect of news media this paper exploits the published news articles in popular newspaper from India namely, THE HINDU. We generate a new network which only considers nodes and edges from GTD network. If two nodes are co-occurring in an article we put an edge between the node pair. Since this network is built particularly over the GTD network with THE HINDU, we name this network as ${GTD}_{HINDU}$ .

From earlier studies [8,32], it can be inferred that incorporating temporal changes by different attributes and various relationships may result in better performance in estimating centrality, link prediction, etc. For example in counter-terrorism, recent activity of terrorist organizations may be of more importance than their past behavior. To incorporate this we further create a tensor GTD network ( ${GTD}_{Freq}^{T}$ ) and a Tensor activeness vector ( ${GTD}_{Act}^{T}$ ) which gives more importance to recent relationships in GTD and node frequency from GTD respectively. To be precise, for ${GTD}_{Freq}^{T}$ , we divide the GTD network into ten different snapshots where a particular snapshot represents a network for one year (i.e. 2000, 2001, etc.). In the similar way, for ${GTD}_{Act}^{T}$ , we divide the frequency of different nodes year wise which results in ten activeness vectors. Now, ${GTD}_{Freq}^{T}$ and ${GTD}_{Act}^{T}$ is constructed using the following method:

Suppose the dataset is divided in $X_{1}$ to $X_{T}$ matrices of size $n \times m$ , then the collapsed data from 1 to T is: $\begin{matrix} (6) & E = \sum_{t = 1}^{T} α^{(T + 1) - t} X_{t} \end{matrix}$ where $α \in (0, 1)$ can be chosen by the user. In this study, we have taken 0.8 as the value of α. Similarly, we create a tensor vector in the same manner by considering E and X as vectors.

4.1. Parameters used for ranking nodes using PPR

As discussed in Section 1, one of the objectives of this paper is to study the effects of external information such as, news media ( ${GTD}_{HINDU}$ ) and temporal dynamics of GTD network ( ${GTD}_{Freq}^{T}$ , ${GTD}_{Act}^{T}$ ). To incorporate the influence of external information this study proposes to use node importance obtained using PPR personalized by various external information. From PPR formulation in equation 3, it is evident that it can be adapted for both types of personalization parameter, i.e. matrix and vector by just replacing $I q^{T}$ to ${GTD}_{HINDU}$ or ${GTD}_{Freq}^{T}$ matrix and q to ${GTD}_{Act}^{T}$ vector respectively. Utilizing these three external information and two more vectors consisting of total frequency of nodes (from 2000 to 2009, refer Table 2) and only the recent node frequency (i.e. from 2009) from GTD network, we propose the following five parametric variants of PPR centrality:

${PPR}^{Co}$ : PPR with co-occurrence matrix obtained using ${GTD}_{HINDU}$ as personalization parameter.

${PPR}_{Rel}^{T}$ : PPR with ${GTD}_{Freq}^{T}$ matrix as personalization parameter.

${PPR}_{Act}^{T}$ : PPR with ${GTD}_{Act}^{T}$ vector as personalization parameter.

${PPR}_{Freq}$ : PPR with frequency of nodes during the training period, i.e., during 2000–2009 as personalization vector.

${PPR}_{Recy}$ : PPR with the frequency of nodes in recent past is considered as personalization vector. To estimate the recent frequency of nodes, we select the total frequency of nodes in last one year from training data, i.e. 2009. We chose year 2009 based on the intuition that, node frequency in the nearest year from test data would provide more correct information. However, recent information may also be fine-grained by treating node frequency differently for different days and months using some weighting parameters. For example, while estimating total frequency for the year 2009 one may weight more to the frequency in specific months, nearby dates from a past attack, etc.

5. Experimental observations

This section investigates the ability of parametric Personalized PageRank formulated in Sections 3.2.2 and 3.2.3 for performing various counter-terrorism related analytical tasks without changing the underlying model, but by passing appropriate user-defined personalization parameters. We begin with investigating effect of different personalization parameters of PPR on node importance. Here we analyze the linear dependency between the rank obtained by the model for terrorist organizations with their actual activeness frequency in future (from 2010 to 2014) using Pearson Correlation Coefficient. The study further extends to understand the effect of node importance (node weight) on different proximity based link prediction methods. The link prediction analysis is focused mainly on three heterogeneous relations; (i) relation between terrorist organization and country indicating a future possible attack by organization on a country, gp-cn, (ii) relation between terrorist organization and city indicating a future possible attack by an organization on city, gp-cty, and (iii) relation between terrorist organization and a target type in future attacks, gp-tar. Further, we also investigate the effect of proposed models for predicting relation between homogeneous attributes, namely, gp-gp which shows the adaptability strength of the models.

5.1. Centrality and its correlation with future activities

In network science, centrality measures define the level of prominence of a node in a network. Among various centrality measures, PPR is a flexible random walk based model where the walker visits the nodes under a supervised direction. This section investigates the effect of various formulations of PPR model parameters which potentially provide high correlation with the ground truth (i.e., future activities). For this task, we consider all the terrorist organizations who have attacked during the testing period (i.e., between 2010 to 2014) and ranked them by their frequency of attacks. This ordered list is considered as the ground truth. We, then, estimate Pearson’s correlation between the ground truth and the observed PPR centrality order (estimated from the training data) using various personalized parameters. We investigated five PPR model parameters as described in Section 4.1. These five model parameters are formulated to study the effect of four different aspects; (i) effect of media reporting ( ${PPR}^{Co}$ ), (ii) effect of recent activities ( ${PPR}_{Recy}$ ), (iii) effect of frequency of activities in the past ( ${PPR}_{Freq}$ ), and (iv) temporal effect ( ${PPR}_{Rel}^{T}$ , ${PPR}_{Act}^{T}$ ). Apart from these variants, we have also investigated correlation performance of non-personalized PageRank model.

Table 4
Average AUC score by AA, JC, RA, and CN using weights from ${PPR}_{Freq}$ , ${PPR}_{Recy}$ and their Unweighted estimates

Metric ${PPR}_{Freq}$ ${PPR}_{Recy}$ Unweighted

aa jc ra cn aa jc ra cn aa jc ra cn

gp-cn 0.737 0.679 0.74 0.736 0.75 0.683 0.753 0.75 0.736 0.561 0.7 0.74

gp-cty 0.703 0.58 0.708 0.703 0.733 0.588 0.74 0.732 0.695 0.436 0.52 0.712

gp-tar 0.725 0.672 0.728 0.725 0.733 0.689 0.737 0.732 0.741 0.612 0.687 0.747

Metric	${PPR}_{Freq}$	${PPR}_{Recy}$	Unweighted
gp-cn	0.737	0.679	0.74	0.736	0.75	0.683	0.753	0.75	0.736	0.561	0.7	0.74
gp-cty	0.703	0.58	0.708	0.703	0.733	0.588	0.74	0.732	0.695	0.436	0.52	0.712
gp-tar	0.725	0.672	0.728	0.725	0.733	0.689	0.737	0.732	0.741	0.612	0.687	0.747

Table 5

Average AUC score by AA, JC, RA, and CN using weights from PR, ${PPR}_{Act}^{T}$ , ${PPR}_{Rel}^{T}$ , and ${PPR}^{Co}$

Metric	PR				${PPR}_{Act}^{T}$				${PPR}_{Rel}^{T}$				${PPR}^{Co}$

	aa	jc	ra	cn	aa	jc	ra	cn	aa	jc	ra	cn	aa	jc	ra	cn
gp-cn	0.743	0.649	0.743	0.741	0.742	0.680	0.744	0.741	0.741	0.679	0.743	0.740	0.738	0.649	0.737	0.739
gp-cty	0.705	0.547	0.711	0.702	0.713	0.581	0.717	0.711	0.712	0.581	0.715	0.710	0.682	0.569	0.680	0.683
gp-tar	0.733	0.620	0.739	0.730	0.728	0.677	0.730	0.727	0.727	0.675	0.729	0.726	0.715	0.650	0.719	0.712

The plots in Fig. 2 show correlation between ranking of terrorist organizations using PPR and ranking by the frequency of attacks between year 2010 to year 2014. Since, Fig. 2 is arranged in descending order by the future frequency of terrorist organizations, correlation with only top few is low, but positive. As the number of organization increases, the correlation score is also increased considerably. The motivation for the correlation analysis is to assess the linear dependency between the ranking by proposed models and actual activities by terrorist organizations in future. Further, we validate the ranking performance among all the proposed models over all the terrorist organizations. It is evident from Fig. 2 that appropriate personalization may enhance correlation performance. Moreover, it is observed that over all ranges of the top organization, at least three parametrized models outperform non-parametrized model.

Fig. 2.

Correlation of different ranking models with future attack frequencies (Ground Truth), $K \in (20, 40, 60, \dots, 201)$ .

Further, from the plot, it is clearly visible that temporal based parameters ( ${PPR}_{Rel}^{T}$ and ${PPR}_{Act}^{T}$ ) outperform other models. It also shows that future activities are influenced by their past activities prioritized by their recent activities (tensor formation in equation 6 giving higher importance to recent activities.).

Remarks.

Topological information of a network alone is not sufficient to predict future activities of a terrorist organization. Considering additional information such as historical activities of the organization, media appearance and recent activities etc. along with topological structure helps in predicting future activities.

5.2. Predicting relationship between attack attributes

In the above section, we have investigated correlation between future activities of an organization and topological centralities, historical activities, recent activities, and analyze their responses in predicting future activities. With the close inspection of GTD, we found that terrorist organizations mostly follow the earlier way of attack, target types, etc. To investigate this, we predict repeated future relationships between a terrorist organization and other attributes defining an attack. The proposed heterogeneous network constructed in Definition 1 using the GTD dataset consist of ten number of attribute classes. The proposed framework can potentially study link prediction between all $^{10} C_{2}$ relations. However, this study focuses on three types of relationships; (i) organization attacking a country (gp-cn) consisting 231 relations between 201 terrorist groups and 57 countries, (ii) organization attacking a city (gp-cty) consisting 740 relations between 102 terrorist groups and 656 cities, and (iii) organization attacking on a target type (gp-tar) consisting 522 relations between 169 terrorist group and 10 target types. As defined in Section 3.3, we have considered four localized node proximity based linked prediction methods; common neighbor (CN), Jaccard Coefficient (JC), Adamic Adar (AA) and Resource Allocation (RA). Considering the above five PPR based measure of centrality (see Section 4.1) as well as non parametrized PageRank as node weights, we have investigated their link prediction performance using average AUC score. Average AUC score for testing links is calculated using the following formula [11]: $\begin{matrix} (7) & Avg AUC = \frac{n_{1} + 0.5 n_{2}}{n * p} \end{matrix}$ where $n_{1}$ = number of times link prediction score for existing test edge is greater than other non-existing test edges, $n_{2}$ = number of times link prediction score for existing test edge is equal to other non-existing test edges, n = number of non-existing test edges, and p = number of existing test edges.

Table 4 and Table 5 compare the link prediction performances in terms of Average AUC score for six node centrality setups with the baseline prediction models without considering node weights (Unweighted). Out of 72 prediction cases (six centralities, four prediction models, and three types of relations to be predicted), the proposed node weighed version outperforms unweighted counterparts at least in 70% cases. It shows that node weight helps in improving prediction accuracy. Among the four prediction models, RA dominates the other three models (CN, JC, and AA) in all the setups except for ${PPR}^{Co}$ . While comparing the performance of node weighted RA with that of unweighted counterpart, it clearly shows that node weighted RA (with all six centralities) outperforms the unweighted counterpart. From Table 4 and Table 5, it is evident that node importance has significant contribution while predicting future repeated relations. Prediction score for RA is improved by 7.5% for gp-cn, 42.4% for gp-cty and 7.6% for gp-tar.

Fig. 3.

Average Precision for top 50 predicted relations by RA.

Fig. 4.

Terrorist Attack Distribution over 2000–2014.

While observing significant improvement in prediction performance after considering node importance (as compared to unweighted counterpart), it is observed that the six personalization parameters provide comparable AUC scores. Though we observe significant differences in correlation analysis as reported in Fig. 2, the comparable prediction performance in Table 4 and Table 5 may be due to the averaging effect while estimating AUC scores. To investigate this, we further evaluate the predicted relations using Average Precision at K ( $AP@K$ ). $AP@K$ estimate prediction performance at top predictions (which may be of importance from counter-terrorism perspective) and can be defined as follow: $\begin{matrix} (8) & AP@K = \frac{\sum_{k \in P} Precision@k}{| P |} \end{matrix}$ where $P$ is set of positions of the correct predictions in top K.

Among the four link prediction methods we chose RA as it is at least 70% times better than others (see Table 4 and Table 5).

Figure 3 shows the $AP@K$ for different values of K, i.e. 10, 20, 30, 40, and 50. It is evident that weighted methods (PR, PPR) perform better than unweighted method in predicting all the three relations, i.e. gp-cn, gp-cty, gp-tar in Fig. 3(a), (b), and (c) respectively. It can be inferred from this observation that with appropriate prioritization PageRank based methods can be exploited for better predictions. In almost all the cases ${PPR}_{Recy}$ performs better than others which shows the ability of recent information in predicting future relations. It is also observed that for predicting gp-cn relation ${PPR}^{Co}$ performs better than all others. This observation indicates that co-occurrence of terrorist organization and country on news media influence future attacks. In addition, it also supports the concluding remarks of earlier studies on mutual dependencies between terrorist groups and news media (refer Section 2.2). However, ${PPR}^{Co}$ is observed to be under-performing for predicting gp-cty and gp-tar relations. It may be due to less frequency of co-occurrences for city or target types with the terrorist organizations in news articles, (the experimental dataset limits to THE HINDU publication). With larger media collection from larger sources will provide more stronger inference. This study reports our preliminary observations on limited dataset.

In the above discussion, we have averaged the scores over the entire set of terrorist organizations. However, attack frequency of different organization varies widely. Figure 4 shows attack frequency distribution of different organizations. It clearly shows that very few terrorist organizations carry out majority of the attacks globally. Characteristics of active and less active organizations may be different. To understand such possible patterns, we further analyze $AP@K$ for most active and less active terrorist organizations separately in two ways: (i) Considering only those relations formed by top ten most active terrorist groups, (ii) Relations formed by other least active terrorist groups.

Fig. 5.

Average Precision by RA for Top 50 predicted relations formed by Most Active and Rest of the terrorist organizations.

Table 6

Top five Terrorist Organization Alliance predicted by RA using all the parametric variants of PPR as centrality measures listed in Section 4.1

PR		${PPR}^{Co}$		${PPR}_{Rel}^{T}$		${PPR}_{Act}^{T}$		$Freq$		$Recy$		Unweighted
Taliban	TTP	LTTE	Maoists	Taliban	TTP	Taliban	TTP	Taliban	TTP	Taliban	TTP	AQLIM	GSPC
Maoists	CPI-Maoist	HM	LeT	Maoists	CPI-Maoist	Maoists	CPI-Maoist	Maoists	CPI-Maoist	Maoists	CPI-Maoist	Hamas	PIJ
LTTE	Taliban	LeT	JeM	LTTE	Taliban	LTTE	Taliban	LTTE	Taliban	LTTE	CPI-Maoist	ELN	FARC
LTTE	Maoists	HM	JeM	LTTE	Maoists	LTTE	Maoists	LTTE	Maoists	LTTE	Maoists	FARC	AUC
LTTE	TTP	LTTE	ULFA	LTTE	CPI-Maoist	LTTE	CPI-Maoist	LTTE	TTP	LTTE	Taliban	MILF	NPA

Similar to the observation in Fig. 3, weighted methods perform better than unweighted in almost all the cases for predicting relations contributed by most active and the rest terrorist organizations (refer Fig. 5). It can be also be seen that ${PPR}_{Recy}$ constantly performs better than all the setups while considering relations only from top ten most active groups. However, it always under-performs for the relations considering other least active groups. This observation is intuitive as ${PPR}_{Recy}$ utilizes the recent frequency of terrorist organizations as personalization vector to PPR. It is interesting to note from Fig. 5 that, ${PPR}^{Co}$ under-performs in predicting relations from most active organizations while it constantly performs better in predicting relations by other least active organizations. Hence, it may be inferred that in case of most active terrorist organizations recent attack information is crucial. While media reporting helps in predicting relationship formed by least active terrorist organizations.

Remarks.

Predicting relationship gets better by considering the effect of external information as node weights. However different information sources have different effects. The recent information is important for most active terrorist organization while news media helps in tracking down other least active organizations.

5.3. Predicting top alliance among various terrorist organizations

The terrorist attack network and link prediction methods explored in this study can also be utilized for analyzing potential alliances among terrorist organizations without modifying the underlying framework. It is because, two terrorist organizations may be allies if they have common targets or share a common ideology. Table 6 lists the top five alliances obtained using RA for different parametric PPR as centrality measures. After referring to external sources; (i) Wikipedia pages related to concerned terrorist organizations, (ii) IDSA publications towards the possible alliance, we have manually verified the top observed alliances reported in Table 6. It is observed that almost 60% of the predicted alliances are found to be true (highlighted in Table 6). For example, it is easy to verify from above sources that Maoist, CPI-Maoist, and LTTE help each other in various needs, such as training, finances, etc., and are potential allies.2

²
http://www.idsa.in/idsacomments/Maoistsglobalweboflinkages

In addition, it is also observed that

{PPR}^{Co}

outperforms other prediction models. It shows that incorporating news media reporting helps in determining organizational alliances in a better way.

6. Conclusion

This paper investigates the ability of personalized PageRank over a heterogeneous terrorist attack network for incorporating different forms of personalized parameters to address various aspects of counter-terrorism related issues. Effect of various parametric setups have been investigated using Global Terrorism Database for two important counter-terrorism tasks; (i) prediction of future attack from a terrorist organization, and (ii) prediction of the relationship between a terrorist organization with other attributes (country, city and target types). From various parametric setups, we observe that PPR when personalized with network’s temporal dynamics performs better in predicting future attacks of terrorist organizations. Further it is also observed that incorporating node importance can enhance relationship prediction performance. With RA as link predictor we found that relation prediction score is improved by 7.5% for gp-cn , 42.4% for gp-cty, and 7.6% for gp-tar when compared to unweighted setup as counterpart. It is evident that recent information when used as a personalization parameter improves the relationship prediction.

This study has limited its investigation only for three types of relationships. It can easily be extended to more relationships. Further, this paper has considered only one news publication to study the influence of media discussion on various counter-terrorism tasks. It may be extended to more number of media resources to capture wider spectrum of information and relationship.

References

L.A.

Adamic and

Adar, Friends and neighbors on the web, Social Networks 25(3) (2003), 211–230. doi:10.1016/S0378-8733(03)00009-1.

Anil,

S.R.

Singh and

Sarmah, Personalized PageRank as a method of exploiting heterogeneous network for counter terrorism and homeland security, in: Proc. 2016 IEEE/WIC/ACM International Conference on Web Intelligence (WI), Omaha, NE, 2016, pp. 327–334.

Bennett, News: The Politics of Illusion, Longman, 2001.

Brin and

Page, The anatomy of a large-scale hypertextual web search engine, Computer Networks 30(1–7) (1998), 107–117.

Cao,

Kong and

P.S.

Yu, Collective prediction of multiple types of links in heterogeneous information networks, in: Proc. 2014 IEEE International Conference on Data Mining, Shenzhen, 2014, pp. 50–59. doi:10.1109/ICDM.2014.25.

Chen,

Gao,

Wu and

Li, Tag co-occurrence relationship prediction in heterogeneous information networks, in: Proc. 2013 International Conference on Parallel and Distributed Systems, Seoul, 2013, pp. 528–533. doi:10.1109/ICPADS.2013.95.

Dong,

Tang,

Wu,

Tian,

N.V.

Chawla,

Rao and

Cao, Link prediction and recommendation across heterogeneous social networks, in: Proc. 2012 IEEE 12th International Conference on Data Mining, Brussels, 2012, pp. 181–190. doi:10.1109/ICDM.2012.140.

D.M.

Dunlavy,

T.G.

Kolda and

Acar, Temporal link prediction using matrix and tensor factorizations, ACM Trans. Knowl. Discov. Data 5(2) (2011), 1–27. doi:10.1145/1921632.1921636.

L.C.

Freeman, Centrality in social networks conceptual clarification, Social Networks 1(3) (1978), 215–239. doi:10.1016/0378-8733(78)90021-7.

10.

Y.Z.

Guo,

Ramamohanarao and

L.A.F.

Park, Personalized PageRank for web page prediction based on access time-length and frequency, in: Proc. IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, Fremont, CA, 2007, pp. 687–690.

11.

J.A.

Hanley and

B.J.

McNeil, The meaning and use of the area under a receiver operating characteristic (roc) curve, Radiology 143(1) (1982), 29–36. doi:10.1148/radiology.143.1.7063747.

12.

T.H.

Haveliwala, Topic-sensitive pagerank, in: Proc. 11th International Conference on World Wide Web, Honolulu, Hawaii, USA, 2002, pp. 517–526.

13.

B.Q.

Hung,

Otsubo,

Hijikata and

Nishida, HITS algorithm improvement using semantic text portion, Web Intelligence and Agent Systems: An International Journal 8(2) (2010), 149–164.

14.

Jaccard, Bulletin del la Société Vaudoise des Sciences Naturelles.

15.

B.M.

Jenkins, The New Age of Terrorism, RAND Corporation, CA, 2006.

16.

Jetter, Terrorism and the media, Contemporary Sociology 22(3) (2014).

17.

Katz, A new status index derived from sociometric analysis, Psychometrika 18(1) (1953), 39–43. doi:10.1007/BF02289026.

18.

Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM 46(5) (1999), 604–632. doi:10.1145/324133.324140.

19.

Krebs, Mapping networks of terrorist cells, CONNECTIONS 24(3) (2002), 43–52.

20.

Li,

Shi,

P.S.

Yu and

Chen, Hrank: A path based ranking method in heterogeneous information network, in: Proc. 15th International Conference on Web-Age Information Management, 2014, pp. 553–565.

21.

Liben-Nowell and

Kleinberg, The link prediction problem for social networks, in: Proc. 12th International Conference on Information and Knowledge Management, New Orleans, LA, USA, 2003, pp. 556–559.

22.

Lin,

Yun and

Zhu, Link prediction using BenefitRanks in weighted networks, in: Proc. 2012 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, Macau, 2012, pp. 423–430.

23.

F.C.

Linton, A set of measures of centrality based on betweenness, Sociometry 40(1) (1977), 35–41. doi:10.2307/3033543.

24.

Liu and

Lu, Link prediction based on local random walk, Europhysics Letters (EPL) 89(5) (2010). doi:10.1209/0295-5075/89/58007.

25.

Liu,

Yu,

Guo and

Sun, Meta-path-based ranking with pseudo relevance feedback on heterogeneous graph for citation recommendation, in: Proc. 23rd ACM International Conference on Conference on Information and Knowledge Management, Shanghai, China, 2014, pp. 121–130.

26.

Lumbaca and

D.H.

Gray, The media as an enabler for acts of terrorism, Global Security Studies 2(1) (2011), 45–54.

27.

A.K.

Menon and

Elkan, Link prediction via matrix factorization, in: Proc. 2011 European Conference on Machine Learning and Knowledge Discovery in Databases, Athens, Greece, 2011, pp. 437–452.

28.

Murata and

Moriyasu, Link prediction of social networks based on weighted proximity measures, in: Proc. IEEE/WIC/ACM International Conference on Web Intelligence, Fremont, CA, 2007, pp. 85–88.

29.

S.A.

Myers,

Zhu and

Leskovec, Information diffusion and external influence in networks, in: Proc. 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China, 2012, pp. 33–41.

30.

B.L.

Nacos, Terrorism/counterterrorism and media in the age of global communication, in: United Nations University Global Seminar Second Shimame-Yamaguchi Session Terrorism – a Global Challenge, 2006, pp. 1–19.

31.

National Consortium for the Study of Terrorism and Responses to Terrorism (start), Global terrorism database.

32.

R.K.

Pan and

Saramäki, Path lengths, correlations, and centrality in temporal networks, Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics 84(1) (2011).

33.

Pearson, The problem of the random walk, Nature 72 (1905).

34.

Peresin, Mass media and terrorism, Impact Strategic 13 (2007), 5–22.

35.

Ressler, Social network analysis as an approach to combat terrorism: Past, present, and future research, Homeland Security Affairs 2 (2006).

36.

J.A.

Rodriguez, The March 11 th terrorist network: In its weakness lies its strength.

37.

Sageman, Understanding Terror Networks, University of Pennsylvania Press, 2004.

38.

Sett,

S.R.

Singh and

Nandi, Influence of edge weight on node proximity based link prediction methods: An empirical analysis, Neurocomputing 172 (2016), 71–83. doi:10.1016/j.neucom.2014.11.089.

39.

Shi,

Li,

Zhang,

Sun and

P.S.

Yu, A survey of heterogeneous information network analysis, IEEE Transactions on Knowledge and Data Engineering 29(1) (2017), 17–37. doi:10.1109/TKDE.2016.2598561.

40.

M.K.

Sparrow, The application of network analysis to criminal intelligence: An assessment of the prospects, Social Networks 13 (1991), 251–274. doi:10.1016/0378-8733(91)90008-H.

41.

Sun,

Barber,

Gupta,

C.C.

Aggarwal and

Han, Co-author relationship prediction in heterogeneous bibliographic networks, in: Proc. 2011 International Conference on Advances in Social Networks Analysis and Mining, Kaohsiung, Taiwan, 2011, pp. 121–128. doi:10.1109/ASONAM.2011.112.

42.

Sun,

Han,

C.C.

Aggarwal and

N.V.

Chawla, When will it happen?: Relationship prediction in heterogeneous information networks, in: Proc. 5th ACM International Conference on Web Search and Data Mining, Seattle, Washington, USA, 2012, pp. 663–672.

43.

Taskar,

Wong,

Abbeel and

Koller, Link prediction in relational data, in: Proc. Advances in Neural Information Processing Systems, British Columbia, Canada, 2003, pp. 659–666.

44.

M.H.

Tsai,

Aggarwal and

Huang, Ranking in heterogeneous social media, in: Proc. 7th ACM International Conference on Web Search and Data Mining, New York, USA, 2014, pp. 613–622. doi:10.1145/2556195.2556254.

45.

B.N.

Uchino, Understanding the links between social support and physical health: A life-span perspective with emphasis on the separability of perceived and received support, Perspectives on Psychological Science (2009), 236–255. doi:10.1111/j.1745-6924.2009.01122.x.

46.

Yang,

N.V.

Chawla,

Sun and

Han, Predicting links in multi-relational and heterogeneous networks, in: Proc. IEEE 12th International Conference on Data Mining, Brussels, Belgium, 2012, pp. 755–764.

47.

Yang,

Tang,

Keomany,

Zhao,

Li,

Ding,

Li and

Wang, Mining competitive relationships by learning across heterogeneous networks, in: Proc. 21st ACM International Conference on Information and Knowledge Management, Maui, Hawaii, USA, 2012, pp. 1432–1441.

48.

Yu,

Gu,

Zhou and

Han, Citation prediction in heterogeneous bibliographic networks, in: Proc. 2012 SIAM International Conference on Data Mining, Anaheim, California, 2012, pp. 1119–1130. doi:10.1137/1.9781611972825.96.

49.

Zhou,

Lü and

Zhang, Predicting missing links via local information, The European Physical Journal B – Condensed Matter and Complex Systems 71(4) (2009), 623–630. doi:10.1140/epjb/e2009-00335-8.

Mining heterogeneous terrorist attack network using personalized PageRank

Abstract

Keywords

1. Introduction

1 https://www.start.umd.edu/gtd

2.1. SNA for counter-terrorism

2.2. Media and terrorism

2.3. Link prediction in Heterogeneous Information Network (HIN)

2.4. Centrality measures in HIN

3. Proposed framework

Definition 1 (Weighted HIN).

3.2. Node importance and centrality measures

3.2.1. Random walk based method

3.2.2. Personalised PageRank for heterogeneous network

3.3. Link prediction

5. Experimental observations

5.1. Centrality and its correlation with future activities

2 http://www.idsa.in/idsacomments/Maoistsglobalweboflinkages

References

¹
https://www.start.umd.edu/gtd

²
http://www.idsa.in/idsacomments/Maoistsglobalweboflinkages