1. Introduction

EBO (effects-based operation) refers to a process for achieving strategic goals by focusing on effects rather than attrition- based destruction [17]. Desired effects in EBO can be accomplished through precise attacks on key targets of adversary systems with minimum risk and destruction.

While some studies have made a great deal of progress in defining and developing the concept of EBO [4, 20], significant gaps still exist in our understanding of EBO. First, previous studies have focused on developing the procedures of and identifying the preconditions for implementing EBO. Although these conceptual works contribute to our knowledge of factors that may underlie EBO, more research attention is needed toward analyzing an adversary’s (enemy’s) complex network. Because the strategic elements of the adversary are linked to each other, analyzing the adversary's network structure is important for both maximizing desired effects and minimizing possible costs of war. Second, several studies have attempted to analyze the adversary’s network structure, but have failed to consider various types of network characteristics. They have mainly used degree centrality which implies the extent to which a node is connected to other nodes [16, 23]. However, there are other types of network centrality. Different types of network centrality provide different bases for assessing the relative importance of nodes [13]. Finally, previous research has paid little attention to the dynamic nature of network structures. The adversary’s network structure may change if some nodes of the network are attacked, because nodes within the adversary’s network are lined to each other. Some researchers have attempted to select key targets based on the network centrality analysis, but these efforts have not yet been jointly examined the dynamic nature of network structures.

The primary purpose of this study is to identify key nodes in an adversary network for implementing EBO successfully. In the previous studies, the methods identifying key nodes have mostly relied on the analysis of network centrality, not taking into account the dynamic nature of network structures. The main contribution of our study is to consider identifying key nodes by adopting an optimization model to capture node value changes if some of the nodes are removed from a network (i.e., to capture the dynamic nature of a network structure), in addition to network centrality analysis. We combine network centrality and the optimization model to identify the most influential nodes. To discuss this in more detail, we first employ the two types of network centrality, degree and betweenness centrality, in order to analyze the adversary’s network structure. Then, we use these centrality results as the influence values of the nodes, and propose an optimization model, formulated as a linear integer program, to find the most influential nodes. It turns out that key node identification based on our optimization model outperforms simple centrality-based node identification in terms of decreasing the entire adversary's network value.

This paper is organized as follows. In Section 2, we provide the literature review related to the concept of EBO and key node identification methods. After describing the dataset, we analyze two types of network centralities and compare the results of each network analysis in Section 3. Section 4 provides a linear integer programming formulation for optimal target selection in EBO. We conclude our study in Section 5.

2. Literature Review

2.1 Conceptual development for target selection in EBO

Recent development of technology has led to more effective and efficient implementation of EBO by providing nearly omniscient intelligence systems and smart weapons enabling pinpoint destruction. In general, the process of EBO includes three phases: planning, execution, and assessment [21]. In the planning phase, the most important objective is to define desired effects. To do this, it is necessary to analyze a PMESII (political, military, economic, social, infrastructure, information) system of an adversary (see <Figure 1>). Because nodes which constitute a PMESII system are linked to each other, by analyzing their connectiveness and network structure, it is possible to identify key nodes. Based on the results of network analyses, actions on key nodes for achieving desired effects are taken by the instruments of national power such as diplomacy, information, military, and economy in the execution phase. After actions on key targets of adversary, it is necessary to conduct a battle damage assessment. In this assessment phase, the focus of assessment should be on the desired effects.

As discussed above, identifying the most influential nodes should be an overriding concern in the process of EBO. Most studies [19, 24] have regarded degree centrality as a proxy for influence values of nodes assuming that key targets are those linked to a greater number of other nodes. However, only using degree centrality in selecting key nodes may not be sufficient to provide information for decision making, and may even be problematic. For example, according to the result of degree centrality analysis, in Figure 2, node C and node D can be selected as key targets because they have the most number of links. Despite not having a central position, however, node A could play an important role in the network by connecting node C and node D. This bridging benefit can be estimated by betweenness centrality analysis rather than degree centrality analysis. Accordingly, we propose both degree centrality and betweenness centrality to identify influential nodes in an adversary network.

We argue that there are optimal priorities of the nodes that maximize desired effects in EBO. However, the node priorities simply obtained from centrality analyses is insufficient to select key targets, because nodes in an adversary network interact with each other through their links. A certain node’s destruction make that node vanished from the network, and the influence values of the remaining nodes will change in the resilient network. Thus, it is important to consider the dynamic nature of network structures resulting from attacks on some nodes.

2.2 Key Node Identification in a Network

Many relationships in the real world can be represented in the form of networks; social networks, logistics networks, transportation networks, power grids, economic networks, biological networks, etc. Due to the interconnections and interrelationships of the nodes in a network, node importance recognition is of special importance in terms of the network's robustness, survivability, and sustainability. In recent years, many influential node identification algorithms for complex networks have been proposed, but most of the studies rely on analyzing topological structures of networks; degree centrality [1], betweenness centrality [15], closeness centrality [6], eigenvector centrality [14], PageRank [18], Katz centrality [8], and k-shell decomposition method [9]. Although these methods are relatively simple to identify key nodes in a network, they all concentrate on the connectivity of a node in a network and so they do not guarantee always to provide us with key nodes globally and dynamically. To overcome such drawback, some researchers have suggested the aggregation or combination of some of these centrality methods; DSHC [25], DKSN and KSD [12], and ALSI [22]. <Table 1> summarizes the methods mentioned above to identify key nodes in networks from the literature.

In this study, we use both centrality analysis and optimization model. After analyzing network centrality to find the most influential nodes in a network, we then use these as input data in our optimization model. By capturing the dynamic nature of the network structure, the suggested optimization model provides the different key nodes from the simple centrality-based key nodes with higher effects.

3. Analyzing Network Centrality

3.1 Data

In this study, we use the EBO network data of Yaman and Polat [24] to identify key nodes as targets. They construct an EBO network for the operation of NATO (the North Atlantic Treaty Organization) to stabilize a country, and they measure the influence values of nodes in this EBO network via a fuzzy cognitive map (FCM) approach. An FCM is a methodology used to model complex systems under the idea of fuzzy logic and neural networks [3]. As shown in <Figure 3>, the structure of the network consists of three layers. The highest- level layer represents a strategic objective. Nodes in the second-level layer are three main effects (A, B, and C) to support the strategic objective. In the bottom-level layer, there are 12 nodes. These nodes play a crucial role in achieving the strategic objective successfully by utilizing the three main effects. Each node in the bottom-level layer not only contributes to one of the three main effects, but is connected to other bottom-level nodes. This yields that destroying a node in the bottom level can change the main effects as well as influence values of nodes of some other nodes, which may cause an overall network structure change, the so-called “dynamic nature of the network structure.” Meanwhile, the strategic objective and main effects are non-existent nodes, and thus, we can only target the bottom-level nodes in this network. Yaman and Polat [24] also identify the weights of links in the network as in <Table 2?, and we use these to analyze network centrality. Here, link weight indicates the proportion with which the influence value of a node affects its neighbouring nodes. If a link weight is not zero, then there exists a link connecting these two nodes with the corresponding weight. For example, node 1 is linked to node 2 with the weight of 0.2517, while node 2 is linked to node 1 with the weight of 0.1392. The weight will play out for delivering one node’s influence value to its neighbouring nodes by the amount of the connecting link weight (proportion). The way on how to transmit the influence values will be discussed later.

Yaman and Polat [24] provide a good causal network structure related to EBO, and their approach for obtaining node values and link weights through FCM should be of special interest. Our study basically employs their network structure and dataset. However, we perform additional analyses through several centrality concepts, and further, select the targets that maximize desired effects using an optimization model.

3.2 Measure

Degree centrality captures the number of links a focal node in a network. In order to compare the results of degree centrality analysis and betweenness centrality analysis, we normalize degree centrality by dividing degree centrality scores by the maximum possible degree. According to data representation, a network can be classified into binary or valued network. A link weight in a binary network only takes 0 or 1, depending on whether the link exists. On the other hand, a valued network can take continuous link weights to represent the degree of link. In the case of valued networks, degree centrality depends on the group size and maximum link strength as well as the number of links [16, 23]. Thus, degree centrality (DC) of node i is calculated according to the following formula:

where w_ij is the weight of the link between node i and j, w_max is a maximum link value, n is a network size (the total number of nodes), and the possible maximum network centrality is 100. For example, from Table 2, the out-degree centrality of node 1 is 40.21 [3.68÷(0.8321×11)].

Betweenness centrality captures the sum of the fraction of shortest paths between two nodes that pass through a focal node. As with degree centrality, we normalize betweenness centrality by dividing betweenness centrality scores by the maximum possible betweenness. Of the several measures of betweenness centrality, we take flow betweenness centrality because our network data comprise valued types of links [5]. Flow betweenness centrality (FBC) is calculated as follows:

where f_jk is the amount of flow between node j and k, and f_jk (i) is the portion of this flow mediated by the node i (see [5] for more detailed discussion and formula). We compute betweenness centrality using Ucinet program [2].

For non-symmetric network data, the in-directed link is the link received by a focal node and the out-directed link is the link initiated by a focal node. Because network data in this study is non-symmetric, we analyze an in-directed network and an out-directed network separately, and then aggregate them.

3.3 Results

<Table 3> presents the results of the network centrality analyses. According to the result of the degree centrality analysis, node 1 is the most influential node, followed by node 2, 6, 7, 9, 10, 11, 4, 8, 3, 5, and 12. However, in the result of the betweenness centrality analysis, node 2 is the most influential node, followed by node 7, 4, 1, 10, 6, 3, 9, 8, 11, 5, and 12. Specifically, node 1 is the highest ranked node in the degree centrality analysis, but ranked lower than node 2 in the betweenness centrality analysis. These different results indicate that only using one type of network centrality is insufficient and that different network centrality analyses should be used to identify influential nodes in EBO.

4. Optimizing Target Selection

In order to identify key nodes, we may simply give ranks to nodes according to centrality analysis results. However, these do not consider the dynamic nature of the interactions of the nodes in a network. In fact, the change of a single node influence value also affect other node’s influence values. For instance, node 2, 7, and 4 based on the betweenness centrality results are not necessarily the best three targets, because destroying the highest betweenness centrality nodes does not always guarantee the most desired effects.

In this section, we discuss how to reflect such changes in a network structure after taking centrality results as the influence values. Adapting the FCM of Yaman and Polat [24], we provide a formulation in which an influence value of a node is recomputed. Moreover, as a final stage of our decision-making, we select the most influential targets (nodes) in an adversary network to make their combat ability incapable or at least degraded. Under the situation that our available attack resource is limited, we consider which nodes with higher priorities to be selected as targets, based on solving the optimization model formulated as a linear integer program.

4.1 Node Influence Values

Let υ_i be the initial influence value of node i. An initial value is taken from one of the centrality results. As seen in <Table 3>, there are three types of initial influence values: degree centrality, betweenness centrality, and their aggregated centrality. We independently use each as our initial value, in turn. Now, we introduce our decision variables as follows:

Furthermore, when node i is selected as a target assuming that it is damaged with a certain percentage, an influence value of node i is decreased by that percentage. This also affects the nodes to which it is connected. Therefore, attack of a single node causes chain effect to not only its neighboring nodes but overall nodes in a network. Consequently, this reduces the main effects of an adversary and then makes the strategic objective unsuccessful.

Let p_i be the percentage of damage to node i (where 0 ≤ p_i ≤ 1, for all i) if it is attacked. Then, if node i is attacked, its remaining influence value becomes υ_i (1 - p_i) . For example, if one node has its initial influence value of 10 with 80% damage of its value when attacked, its “post-value” becomes 10 × (1 - 0.8) = 2. For simplicity, we set damage percentage to be identical to all nodes, e.g., p_i = p for all i. Now, we involve our decision variable to this form. Due to its characteristic that it takes 0 or 1, υ_i (1 - p_ix_i ) leads to an appropriate influence value for node i. Thus, when x_i = 1, the corresponding node value becomes υ_i (1 - p_i ) . Otherwise, it maintains its initial value υ_i .

To take into account interactions between nodes, we employ the notion of an FCM approach [10]. The main idea is that a certain node’s influence value can be calculated via the sum of all incoming node with the proportion of the corresponding link’s weight. In a general form, this can be expressed as Equation (1):

where function f can vary depending on the problems, but usually sets to be bivalent, trivalent, logistic, or sigmoid [24]. As a variant, Yaman and Polat [24] propose Equation (2) by involving its own value into calculation:

This implies that initial value of itself plus incoming node values with the corresponding link’s weight can create a new value of the node. Note that in their approach all node values range from 0 to 1, and the sum of incoming node values are only reflected by the amount of complementary value of itself (1 - υ i o l d) in order to ensure the resulting value is still in [0, 1]. Prior to this approach, Koulouriotis et al. [11] suggest a simpler version of node influence evaluation as Equation (3):

in which incoming node values are no more rescaled by (1 - υ i o l d ) and thus, the new influence value can be obtained by adding incoming node values with weights to its own initial value. Based on these approaches, we employ Formula (4) as our influence value evaluation:

Now, we involve our decision variables on whether to attack node i or not. Then, the final value of node i becomes Equation (5):

We define this as V_i (x) , whose value depends on decision vector x = (x₁, x₂, ⋯, x_n) and accordingly depends on its neighbors’ damages. Let J be the set of all nodes, and i and j be an element of set J , i.e., i,j∈J . In addition, we define J_i as the subset of J whose elements are the incoming nodes to i. Using these sets and indices, Equation (5) can be rewritten as Equation (6):

4.2 Optimization Models for Selecting Nodes

We now select key nodes in a way that combines network centrality analyses and network optimization. As in our EBO network, there is a single highest-level node representing a strategic objective that an adversary pursues. To achieve the strategic objective, there are three main effects on the second highest-level. We denote these effects by node A, B, and C. Since these three nodes are also affected by 12 lowest-level nodes, their post-values can be expressed as V_A (x) , V_B (x) and V_C (x) , respectively. As an attacker, we wish to minimize their effects by targeting some of the lowest-level nodes. This yields the following objective function:

In our EBO network, node A is influenced by node 1 through 5, node B by node 6 through 8, and node C by the others. Taking this into account,

where r_i is a contribution rate of node i. Contribution rates from each node to effect are provided by Yaman & Polat [24] as in <Table 4>.

Now, we consider the situation under which we are not able to attack all of adversary’s nodes, due to resource availability (e.g., guns or missile). So the following cardinality constraint is added to the model:

where k is a constant we can set. The underlying assumptions of this constraint are 1) there is a single type of means of attack, and 2) it is not allowed to attack multiple times for a single target. We provide a final version of our optimization model (7) formulated as an integer program in the following:

s.t.

In sum, Equation (7a) minimizes the sum of main effects of the adversary, Constraint (7b) refers to the influence value evaluation for each node in a recursive way by considering all other nodes, and Constraints (7c)–(7d) clarify disallowance of attacking more than availability and multiple time attacks under a single type of means.

4.3 Computational Results

We show the performance of our optimization model through computational experiments, using the EBO network as in <Figure 1> with the link weights (w_ij) in Table 3. Our optimization model (7) requires several experimental settings. First, an initial influence value of node i, υ_i, is adopted from degree centrality and betweenness centrality obtained in Section 3. We set up three different values for υ_i : 1) degree centrality, 2) betweenness centrality, and 3) aggregate centrality (degree centrality plus betweenness centrality), so that we can compare the node priorities and effects with the ones determined via optimization model. Finally, damage percentage (p_i) is set to be 0.8 for all nodes identically. In Constraint (7c), we use the value of k from 1 to 12, in turn. This enables to see the node priorities (or, rankings) to minimize the adversary’s effects. Moreover, an optimal objective value after solving the optimization model gives the adversary’s remaining effects, and thus, it is possible to compare the effect decreases and marginal decrease value under the two different node selection approaches: Centrality-based node selection and optimal target selection. The former simply selects the nodes with high centrality and the latter optimally selects nodes in a way that minimizes the effects.

We show the resulting node priorities by solving the optimization model and compare these with the simple centrality- based priorities in <Table 5>.

These results imply that depending on the notion of centrality considered, selected targets can vary. In particular, degree centrality and betweenness centrality provide more distinguishable results. If the goal is to decrease or degrade the influence value, then degree centrality based results would be more appropriate selection. However, the goal to disconnect the nodes may make one choose betweenness centrality based priorities.

In addition, under a certain centrality, optimal node priorities can be achieved by solving the optimization model, and this definitely outperforms simple centrality-based rankings in terms of decreasing the entire network value. Figure 4 shows the remaining values as the number of targets grows large. If the influence value is based on degree centrality, the solution qualities are not so remarkable although we achieve optimality for the best target selection. However, when focusing on a betweenness centrality-based influence value, an optimal target selection provides a relatively promising result. This can be interpreted: If betweenness centrality is the measure for evaluating the influence values of nodes, the network structure and their interdependency seem to be more dynamic, i.e., one node’s effect change or its removal from the network can highly affect other nodes, leading to drastic change of priorities. Moreover, in such a dynamic nature, selecting the most influential nodes via an optimization model rather than centrality analysis can always assure the best response in supporting decision making.

5. Conclusion

In this study, we have discussed a network-based approach for effective target selection. First, an EBO network was analyzed using degree centrality and betweenness centrality in order to see which nodes are more likely to be influential, since network centrality is considered as a proxy for evaluating the influence value of nodes. Second, considering the initial influence node values obtained from centrality analysis, we present an optimization model taking into account the dynamic nature of the network structure.

Through our computational results, different types of network centrality enable us to view the same network from different angles. While degree centrality prioritizes nodes with higher direct connections, betweenness centrality gives nodes with higher indirect connections (i.e., high bridging role) high ranks. And, the results show that under betweenness centrality, nodes are ranked quite differently from the ones of degree centrality. Moreover, our optimization model can capture the dynamic nature of network structure by taking the so-called post value into consideration. Target selection via our optimization model clearly outperforms the selection from simple centrality-based target selection regarding the entire network value decrease.

Despite the results of this study, several limitations should be addressed for future research. First, we adopted the test network data from one of the early studies of EBO. In the future research, more generalized network structures and sizes should be considered. Furthermore, the optimization model that we present is also customized for solving the problem of the used test network. In the future, more generalized optimization models are needed to solve various types of networks. Next, one may think that on the adversary's perspective, they may assess our EBO network to select our infrastructures as their targets. For our defense strategy or tactics, game theoretic approach could be an option that deals with such a problem. Finally, we used deterministic input parameters (i.e., all input data are given in advance), which may not be that realistic. Assuming one or more of these to be stochastic (or, probabilistic) would yield more advanced, practical models. We leave such considerations for future research.

Our approach makes no claims about comprehensiveness. That said, what we suggest here is a new perspective on a topic of enduring interest in EBO. We expect that these results can provide insight not only to military field for choosing key targets, but also to other multidisciplinary areas in identifying key nodes when they are interacting to each other in a network.