# Approximation of Interactive Betweenness Centrality in Large Complex Networks

Authors: Sebastian Wandelt; Xing Shi; Xiaoqian Sun
Journal: Complexity
 (2020)

---

## Abstract

The analysis of real-world systems through the lens of complex networks often requires a node importance function. While many such views on importance exist, a frequently used global node importance measure is betweenness centrality, quantifying the number of times a node occurs on all shortest paths in a network. This centrality of nodes often significantly depends on the presence of nodes in the network; once a node is missing, e.g., due to a failure, other nodes’ centrality values can change dramatically. This observation is, for instance, important when dismantling a network: instead of removing the nodes in decreasing order of their static betweenness, recomputing the betweenness after a removal creates tremendously stronger attacks, as has been shown in recent research. This process is referred to as interactive betweenness centrality. Nevertheless, very few studies compute the interactive betweenness centrality, given its high computational costs, a worst-case runtime complexity ofO(N∗∗4) in the number of nodes in the network. In this study, we address the research questions, whether approximations of interactive betweenness centrality can be obtained with reduction of computational costs and how much quality/accuracy needs to be traded in order to obtain a significant reduction. At the heart of our interactive betweenness approximation framework, we use a set of established betweenness approximation techniques, which come with a wide range of parameter settings. Given that we are interested in the top-ranked node(s) for interactive dismantling, we tune these methods accordingly. Moreover, we explore the idea of batch removal, where groups of top-k ranked nodes are removed before recomputation of betweenness centrality values. Our experiments on real-world and random networks show that specific variants of the approximate interactive betweenness framework allow for a speedup of two orders of magnitude, compared to the exact computation, while obtaining near-optimal results. This work contributes to the analysis of complex network phenomena, with a particular focus on obtaining scalable techniques.


---

## Body

## 1. Introduction

Complex network theory provides powerful tools to understand the structures and dynamics of many complex systems. Essentially, these systems are being modelled as nodes representing entities and links representing dependencies between entities. Much research effort has been spent on understanding different types of critical infrastructure systems, e.g., energy [1, 2], communication [3, 4], air transportation [5–8], railway [9], and social networks [10]. The phenomena and processes analyzed on these networks vary by study, including resilience analysis [11, 12], delay/information spreading [13–15], growth pattern analysis, and many others. Nevertheless, at the heart of many analysis tasks is the problem of identifying node importance, i.e., a quantification of the relative value of a node in a network. Indeed, it is significant to identify the extremely important nodes which maintain the structure and function of the network.These node importance values vary for two reasons. First, the importance can be measured regarding different perspectives of importance, preferring local vs global or topological vs flow-like views. Depending on the chosen view, many different node centrality measures have been proposed, including degree centrality, closeness centrality [16], eigenvector centrality [17], Katz centrality [18], and betweenness centrality [19]. Second, the importance of a node often depends significantly on the presence of other nodes in the network. For a pair of nodes with redundant function, e.g., regarding propagation, one node can become significantly more important in the absence of the other node. This effect is visualized in Figure 1. Initially, node 9 is not important in the network. However, once node 14 fails, the majority of flow in the network is routed via node 9, since all flows have to go through the remaining path on the right-hand side. Accordingly, a very small change in the network, here referring to the failure of a node, can change the node importance significantly.Figure 1
Static betweenness attack and interactive betweenness attack on an example network. The node with the highest betweenness is highlighted with larger node size. The red node represents the attacked node in each subplot.Existing methods usually do not take into account this dependency of node importance values, mainly because of limited computational resources. For instance, computing exact betweenness centrality values of each node in a network has a worst-case time complexity cubic in the number of nodes, since essentially, all pairs of shortest path between all nodes have to be computed [20]. Computing the interactive betweenness centrality requires to recompute the betweenness centrality after each node removal, increasing the worst-case time complexity to being quartic in the number of nodes in the network, i.e., ON4. Such a high computational complexity inhibits computations on even medium-sized networks, given that increasing the size of a network by a factor of 10 will increase the required computational resources by a factor of 10,000. While static betweenness centrality computations can be speed up significantly by parallelization [21], interactive betweenness centrality cannot be further accelerated, given the dependency of choices between each attack step: the subnetwork at step i+1 is only determined once the to-be-removed node at step i is fixed.In this study, we aim to explore possibilities for computing an approximation of the interactive betweenness centrality for larger networks. To achieve this goal, we devise an estimation framework. We exploit betweenness approximation techniques for selecting outstandingly important nodes in a network. There are several widely used static betweenness approximation methods, which come with whole range of parameters. Moreover, in order to avoid recomputing the approximate betweenness at each iteration, we select a number of outstanding nodes (not only one) on the fly. Experiments on random and real-world networks show that this strategy computes rankings very similar to those obtained by exact interactive betweenness computation. Moreover, experiments on network dismantling show that the results obtained by approximation of interactive betweenness are close to those of interactive betweenness, but at much lower runtime requirements. Our work contributes to the analysis of complex network phenomena, with a particular focus on obtaining scalable techniques.


## 2. Methods

### 2.1. The Overall Framework

We devised an interactive betweenness approximation framework consisting of a set of static betweenness approximation algorithms and different selections ofk-batch removal (remove k nodes with high betweenness before recomputation). The exact interactive computation is recomputing betweenness values after removal of the Top-1 node. However, the time complexity of static betweenness computation is ON∗E, where N is the number of nodes and E is the number of edges in the network, which is prohibitive for large networks and makes the interactive computation more expensive. To reduce the computational costs, we exploit approximation methods since such methods can make trade-offs between speed and identification of high betweenness nodes. Note that the identification of the highest betweenness node is the core part of interactive computation. Moreover, we also considered selection of k (i.e., choice of how many nodes to remove in each iteration): instead of removing a single node with the highest betweenness, batch removal reduces the number of iterations of interactive computation. Based on the above ideas, our framework has two core parts:(1)
Static betweenness estimation: compute estimated betweenness values of all nodes in the current GCC (giant connected component) of the network.(2)
Selection of batch removal: obtain Top-k ranked nodes and remove them from the network and then go back to (1).In part (1), the approximation algorithms estimate betweenness values of each node in the current GCC. The accuracy of approximation affects the quality of such interactive computation: if the approximation method cannot identify the Top-k nodes correctly, it will lead to continuous errors in subsequent iterations, which propagate and often become worse with an increasing number of nodes. Therefore, we need to select approximation methods with nice trade-offs between quality and runtime. In part (2), the selection of the parameter k is also worth considering. On the one hand, if we choose small k, we will get better quality. One of the most extreme choices is setting k = 1, that is, recomputing betweenness after each node’s removal, which will be extremely time consuming but can get exact results. On the other hand, if we set k very large, we can reduce runtime for the price of deteriorated quality. In the best case, the k value is chosen adaptively in each iteration, as there may be only one or many high betweenness nodes in the current GCC. To sum up, our interactive betweenness approximation framework focuses on the selections of approximation methods together with the number and size of batch removal.


### 2.2. Static Betweenness Approximation

The existing algorithms for betweenness approximation compute an estimation of the static betweenness of all nodes in the network. Since all the approximation methods are based on Brandes’ algorithm, we revisit this algorithm first. For a node pairs,t, Brandes [20] defines the pair-dependency on node v, denoted by δstv, and dependency of node s on node v, denoted by δs•v, as(1)δstv=σstvσst,δs•v=∑t∈Gδstv.In addition, Brandes proved thatδs•v obeys(2)δs•v=∑t:v∈Pstσsvσst1+δs•t,where Pst represents all parents of t on the breadth-first-search (BFS) from s. Based on these, the betweenness value of vBv can be computed by Bv=∑s∈G,s≠vδs•v. That is, given a network with N nodes and E edges, a single BFS from one source node s can compute the dependency of each node which takes OE time. To obtain betweenness of all nodes, each node of the network should be set as a source node and it requires N iterations of BFS. In total, the computation of exact static betweenness of all nodes needs ON∗E time, which is quite expensive for large networks. Besides, for dense networks with E≈N2, as the worst case, the time complexity is ON3.To reduce the computational cost, approximation methods compute a subset of node dependencies or pair dependencies instead of the set of all dependencies required by the exact computation. Different strategies for selecting the subset constitute several approximating methods. In general, there are three classifications:(1)
Pivots sampling: such methods conduct BFS from a subset of source nodes, calledpivots, and compute node dependencies on each node from selected pivots.(2)
Node pairs sampling: instead of considering node dependencies, such methods sample pairs of nodes and compute the pair dependencies on each node from selected node pairs.(3)
Bounded BFS: such methods change the stop condition of BFS and only consider a subset of shortest paths.Besides these three classifications, there are also some recent methods for betweenness approximation, including the sparse-modeling based method [22], MPI-based adaptive sampling method [23], and GNN-based method [24]. More details for different static approximating methods and parameter settings are in Appendix A.


### 2.3. Choosing the Size of Batch Removal

In this section, we describe more details on how to determinek based on current GCC in each iteration. If k is small, few nodes are removed from current GCC, which requires more iterations and higher computational costs. On the contrary, if k is large, the computational costs will be reduced but the quality decreases since many removed nodes have lost their importance. Therefore, we need to make a trade-off between quality and speed. Note that it is more reasonable to choose an adaptive k value based on the number of particularly central nodes in each iteration. Firstly, we need to roughly estimate the range of k for different networks. We selected k = 1 and conducted experiments of the interactive exact betweenness computation on 48 real-world networks with diverse sizes. We visualize the distribution of p50% (the number of nodes that need to be removed to get 50% GCC reduction) in Figure 2. As shown in Figure 2(a), some larger networks can be cut into 50% with removal of few nodes (e.g., removing no more than 10 nodes can get 50% reduction on a network with size >10,000). Besides, the distribution of p50% in Figure 2(b) indicates that removal of no more than 50 nodes can cause 50% GCC reduction on many networks. When being interested in fixed-size batch removal, we set k ∈ [1, 2, 4, 8, 16].Figure 2
Distribution ofp50% for 48 real-world networks.
(a)
(b)Figure3 shows the distribution of betweenness values under different attack strategies. We can see that in I4 (interactive 4th attack) and IR (interactive remainder), there are 2 nodes with high betweenness (e.g., node 2 and 3 with betweenness value = 0.5 in IR) and these two nodes are of the same importance. We can remove both of them in one iteration to break up the GCC. In I3 (interactive 3rd attack), there is only one node (i.e., node 5) with high betweenness value (0.5), that is, there is only one particularly central node. For such an outstandingly important node, it is reasonable to set k = 1 and only remove the single node from GCC. Inspired by the example network, we, in addition, consider setting k to be the number of nodes with betweenness ≥ 0.5 and make it adaptive in the range 1,2,4,8,16. Besides, we also consider the case of setting k to be the number of nodes with betweenness ≥(average + standard deviation of betweenness values).Figure 3
Distribution of betweenness values of sample network in Figure1. (a) GCC of I2. (b) GCC of I3. (c) GCC of I4. (d) GCC of IR.
(a)
(b)
(c)
(d)Besides, we can remove certain percentage of nodes in each iteration. For the remaining experiments, we selected 1%, 5%, 10%, and 20%. To sum up, we determinek value in each iteration based on the distribution of betweenness values of nodes in current GCC. Table 1 shows an overview of k settings for batch removal.Table 1
Overview ofk settings.
Category
Description
Parameters
Naming
k = constant
Remove constant number of nodes
k in [1, 2, 4, 8, 16]
e.g., 2
k = fraction of nodes
Remove certain fraction of nodes
k in [1%, 5%, 10%, 20%]
e.g., 20%
k = number of nodes with Ba≥B¯b+Sc
Remove all nodes withBa≥B¯b+Sc
Ø
AS
k = adaptived number of nodes with Ba≥0.5
Remove certain nodes withBa≥0.5
Ø and adaptived in [1, 2, 4, 8, 16]
0.5
B
a: betweenness value of one node. B¯b: the average betweenness value in current GCC. Sc: standard deviation of betweenness values in current GCC. dadaptive: k = 2intlog2k1, where k1 represents the number of nodes with betweenness ≥0.5 (e.g., if there are 9 nodes with betweenness ≥0.5, then k = 8).


### 2.4. Measures for Comparison

#### 2.4.1. Accuracy

Given an approximation algorithm and certaink setting, the output of our framework is a ranking of nodes from higher interactive betweenness to lower interactive betweenness. To analyze the approximated ranking, we considered four aspects:(1)
Identification of important nodes: in many cases, people are more concerned about the top nodes with high betweenness. We used three measures: Top-1%-Hits, Top-5%-Hits, and Top-10%-Hits.(2)
Ranking sortedness: compared with the exact ranking, the sortedness of approximated ranking can be described by inversion number.(3)
Weighted coefficient: considering the importance of top-ranked nodes, we used Weightedtau to add the weight of exchanges between top-ranked nodes.(4)
Destructive to the network: during interactive computation, the size of GCC keeps decreasing as we keep removing nodes. A good method can identify nodes with high betweenness, which could have great impact on network connectivity, resulting in a quick dismantling process and a fast GCC reduction. We considered the number of nodes needed to be removed to cut GCC into 10%.In total, we devise six measures to evaluate the accuracy compared to the standard ranking (i.e., the ranking of nodes of exact computation withk = 1) as follows:(1)
Top-1%-Hits: the fraction of nodes correctly identified by approximate methods in Top-1% nodes.(2)
Top-5%-Hits: the fraction of nodes correctly identified in Top-5% nodes.(3)
Top-10%-Hits: the fraction of nodes correctly identified in Top-10% nodes.(4)
Inversion: normalized inversion number of estimated ranking with exact ranking as the standard. After computing the inversion number, we normalized it and mapped it to [0, 1]: inversion =1−2∗inv/N∗N−1, where N is the number of nodes and inv is the exact inversion number.(5)
Weightedtau: a node with ranka is mapped to weight 1/(a + 1) and an exchange between two nodes with rank a and b has weight 1/(a + 1) + 1/(b + 1). That is, top-ranked nodes have higher weights, which increase the impact of the exchanges between important nodes.(6)
10% GCC reduction (p10%): it represents how many nodes the method requires to remove to dismantle the network until GCC < 10% ∗ N. The normalized value p10% is mapped to [0, 1] and 1 means the method which needs the minimum number of nodes to get 10% GCC reduction.


#### 2.4.2. Runtime

We conduct experiments on the same computer with four i7-6500U cores (2.50 GHz) and 16 GB RAM. We run each approximate method independently and recorded the exact runtime.


#### 2.4.3. Trade-Offs

Considering six measures of accuracy, we normalized the runtime and plotted it with normalized measures to see which method can offer a nice trade-off. In order to analyze the results on different networks, we computed the average normalized runtime and measure values. To sum up, we use six measures to evaluate accuracy, and we also analyzed runtime and trade-offs. Besides, we set the naming schedule as approximation algorithm_parameter_k (e.g., RAND2_64_2 represents using RAND2 algorithm with number of pivots = 64 and k = 2).


## 2.1. The Overall Framework

We devised an interactive betweenness approximation framework consisting of a set of static betweenness approximation algorithms and different selections ofk-batch removal (remove k nodes with high betweenness before recomputation). The exact interactive computation is recomputing betweenness values after removal of the Top-1 node. However, the time complexity of static betweenness computation is ON∗E, where N is the number of nodes and E is the number of edges in the network, which is prohibitive for large networks and makes the interactive computation more expensive. To reduce the computational costs, we exploit approximation methods since such methods can make trade-offs between speed and identification of high betweenness nodes. Note that the identification of the highest betweenness node is the core part of interactive computation. Moreover, we also considered selection of k (i.e., choice of how many nodes to remove in each iteration): instead of removing a single node with the highest betweenness, batch removal reduces the number of iterations of interactive computation. Based on the above ideas, our framework has two core parts:(1)
Static betweenness estimation: compute estimated betweenness values of all nodes in the current GCC (giant connected component) of the network.(2)
Selection of batch removal: obtain Top-k ranked nodes and remove them from the network and then go back to (1).In part (1), the approximation algorithms estimate betweenness values of each node in the current GCC. The accuracy of approximation affects the quality of such interactive computation: if the approximation method cannot identify the Top-k nodes correctly, it will lead to continuous errors in subsequent iterations, which propagate and often become worse with an increasing number of nodes. Therefore, we need to select approximation methods with nice trade-offs between quality and runtime. In part (2), the selection of the parameter k is also worth considering. On the one hand, if we choose small k, we will get better quality. One of the most extreme choices is setting k = 1, that is, recomputing betweenness after each node’s removal, which will be extremely time consuming but can get exact results. On the other hand, if we set k very large, we can reduce runtime for the price of deteriorated quality. In the best case, the k value is chosen adaptively in each iteration, as there may be only one or many high betweenness nodes in the current GCC. To sum up, our interactive betweenness approximation framework focuses on the selections of approximation methods together with the number and size of batch removal.


## 2.2. Static Betweenness Approximation

The existing algorithms for betweenness approximation compute an estimation of the static betweenness of all nodes in the network. Since all the approximation methods are based on Brandes’ algorithm, we revisit this algorithm first. For a node pairs,t, Brandes [20] defines the pair-dependency on node v, denoted by δstv, and dependency of node s on node v, denoted by δs•v, as(1)δstv=σstvσst,δs•v=∑t∈Gδstv.In addition, Brandes proved thatδs•v obeys(2)δs•v=∑t:v∈Pstσsvσst1+δs•t,where Pst represents all parents of t on the breadth-first-search (BFS) from s. Based on these, the betweenness value of vBv can be computed by Bv=∑s∈G,s≠vδs•v. That is, given a network with N nodes and E edges, a single BFS from one source node s can compute the dependency of each node which takes OE time. To obtain betweenness of all nodes, each node of the network should be set as a source node and it requires N iterations of BFS. In total, the computation of exact static betweenness of all nodes needs ON∗E time, which is quite expensive for large networks. Besides, for dense networks with E≈N2, as the worst case, the time complexity is ON3.To reduce the computational cost, approximation methods compute a subset of node dependencies or pair dependencies instead of the set of all dependencies required by the exact computation. Different strategies for selecting the subset constitute several approximating methods. In general, there are three classifications:(1)
Pivots sampling: such methods conduct BFS from a subset of source nodes, calledpivots, and compute node dependencies on each node from selected pivots.(2)
Node pairs sampling: instead of considering node dependencies, such methods sample pairs of nodes and compute the pair dependencies on each node from selected node pairs.(3)
Bounded BFS: such methods change the stop condition of BFS and only consider a subset of shortest paths.Besides these three classifications, there are also some recent methods for betweenness approximation, including the sparse-modeling based method [22], MPI-based adaptive sampling method [23], and GNN-based method [24]. More details for different static approximating methods and parameter settings are in Appendix A.


## 2.3. Choosing the Size of Batch Removal

In this section, we describe more details on how to determinek based on current GCC in each iteration. If k is small, few nodes are removed from current GCC, which requires more iterations and higher computational costs. On the contrary, if k is large, the computational costs will be reduced but the quality decreases since many removed nodes have lost their importance. Therefore, we need to make a trade-off between quality and speed. Note that it is more reasonable to choose an adaptive k value based on the number of particularly central nodes in each iteration. Firstly, we need to roughly estimate the range of k for different networks. We selected k = 1 and conducted experiments of the interactive exact betweenness computation on 48 real-world networks with diverse sizes. We visualize the distribution of p50% (the number of nodes that need to be removed to get 50% GCC reduction) in Figure 2. As shown in Figure 2(a), some larger networks can be cut into 50% with removal of few nodes (e.g., removing no more than 10 nodes can get 50% reduction on a network with size >10,000). Besides, the distribution of p50% in Figure 2(b) indicates that removal of no more than 50 nodes can cause 50% GCC reduction on many networks. When being interested in fixed-size batch removal, we set k ∈ [1, 2, 4, 8, 16].Figure 2
Distribution ofp50% for 48 real-world networks.
(a)
(b)Figure3 shows the distribution of betweenness values under different attack strategies. We can see that in I4 (interactive 4th attack) and IR (interactive remainder), there are 2 nodes with high betweenness (e.g., node 2 and 3 with betweenness value = 0.5 in IR) and these two nodes are of the same importance. We can remove both of them in one iteration to break up the GCC. In I3 (interactive 3rd attack), there is only one node (i.e., node 5) with high betweenness value (0.5), that is, there is only one particularly central node. For such an outstandingly important node, it is reasonable to set k = 1 and only remove the single node from GCC. Inspired by the example network, we, in addition, consider setting k to be the number of nodes with betweenness ≥ 0.5 and make it adaptive in the range 1,2,4,8,16. Besides, we also consider the case of setting k to be the number of nodes with betweenness ≥(average + standard deviation of betweenness values).Figure 3
Distribution of betweenness values of sample network in Figure1. (a) GCC of I2. (b) GCC of I3. (c) GCC of I4. (d) GCC of IR.
(a)
(b)
(c)
(d)Besides, we can remove certain percentage of nodes in each iteration. For the remaining experiments, we selected 1%, 5%, 10%, and 20%. To sum up, we determinek value in each iteration based on the distribution of betweenness values of nodes in current GCC. Table 1 shows an overview of k settings for batch removal.Table 1
Overview ofk settings.
Category
Description
Parameters
Naming
k = constant
Remove constant number of nodes
k in [1, 2, 4, 8, 16]
e.g., 2
k = fraction of nodes
Remove certain fraction of nodes
k in [1%, 5%, 10%, 20%]
e.g., 20%
k = number of nodes with Ba≥B¯b+Sc
Remove all nodes withBa≥B¯b+Sc
Ø
AS
k = adaptived number of nodes with Ba≥0.5
Remove certain nodes withBa≥0.5
Ø and adaptived in [1, 2, 4, 8, 16]
0.5
B
a: betweenness value of one node. B¯b: the average betweenness value in current GCC. Sc: standard deviation of betweenness values in current GCC. dadaptive: k = 2intlog2k1, where k1 represents the number of nodes with betweenness ≥0.5 (e.g., if there are 9 nodes with betweenness ≥0.5, then k = 8).


## 2.4. Measures for Comparison

### 2.4.1. Accuracy

Given an approximation algorithm and certaink setting, the output of our framework is a ranking of nodes from higher interactive betweenness to lower interactive betweenness. To analyze the approximated ranking, we considered four aspects:(1)
Identification of important nodes: in many cases, people are more concerned about the top nodes with high betweenness. We used three measures: Top-1%-Hits, Top-5%-Hits, and Top-10%-Hits.(2)
Ranking sortedness: compared with the exact ranking, the sortedness of approximated ranking can be described by inversion number.(3)
Weighted coefficient: considering the importance of top-ranked nodes, we used Weightedtau to add the weight of exchanges between top-ranked nodes.(4)
Destructive to the network: during interactive computation, the size of GCC keeps decreasing as we keep removing nodes. A good method can identify nodes with high betweenness, which could have great impact on network connectivity, resulting in a quick dismantling process and a fast GCC reduction. We considered the number of nodes needed to be removed to cut GCC into 10%.In total, we devise six measures to evaluate the accuracy compared to the standard ranking (i.e., the ranking of nodes of exact computation withk = 1) as follows:(1)
Top-1%-Hits: the fraction of nodes correctly identified by approximate methods in Top-1% nodes.(2)
Top-5%-Hits: the fraction of nodes correctly identified in Top-5% nodes.(3)
Top-10%-Hits: the fraction of nodes correctly identified in Top-10% nodes.(4)
Inversion: normalized inversion number of estimated ranking with exact ranking as the standard. After computing the inversion number, we normalized it and mapped it to [0, 1]: inversion =1−2∗inv/N∗N−1, where N is the number of nodes and inv is the exact inversion number.(5)
Weightedtau: a node with ranka is mapped to weight 1/(a + 1) and an exchange between two nodes with rank a and b has weight 1/(a + 1) + 1/(b + 1). That is, top-ranked nodes have higher weights, which increase the impact of the exchanges between important nodes.(6)
10% GCC reduction (p10%): it represents how many nodes the method requires to remove to dismantle the network until GCC < 10% ∗ N. The normalized value p10% is mapped to [0, 1] and 1 means the method which needs the minimum number of nodes to get 10% GCC reduction.


### 2.4.2. Runtime

We conduct experiments on the same computer with four i7-6500U cores (2.50 GHz) and 16 GB RAM. We run each approximate method independently and recorded the exact runtime.


### 2.4.3. Trade-Offs

Considering six measures of accuracy, we normalized the runtime and plotted it with normalized measures to see which method can offer a nice trade-off. In order to analyze the results on different networks, we computed the average normalized runtime and measure values. To sum up, we use six measures to evaluate accuracy, and we also analyzed runtime and trade-offs. Besides, we set the naming schedule as approximation algorithm_parameter_k (e.g., RAND2_64_2 represents using RAND2 algorithm with number of pivots = 64 and k = 2).


## 2.4.1. Accuracy

Given an approximation algorithm and certaink setting, the output of our framework is a ranking of nodes from higher interactive betweenness to lower interactive betweenness. To analyze the approximated ranking, we considered four aspects:(1)
Identification of important nodes: in many cases, people are more concerned about the top nodes with high betweenness. We used three measures: Top-1%-Hits, Top-5%-Hits, and Top-10%-Hits.(2)
Ranking sortedness: compared with the exact ranking, the sortedness of approximated ranking can be described by inversion number.(3)
Weighted coefficient: considering the importance of top-ranked nodes, we used Weightedtau to add the weight of exchanges between top-ranked nodes.(4)
Destructive to the network: during interactive computation, the size of GCC keeps decreasing as we keep removing nodes. A good method can identify nodes with high betweenness, which could have great impact on network connectivity, resulting in a quick dismantling process and a fast GCC reduction. We considered the number of nodes needed to be removed to cut GCC into 10%.In total, we devise six measures to evaluate the accuracy compared to the standard ranking (i.e., the ranking of nodes of exact computation withk = 1) as follows:(1)
Top-1%-Hits: the fraction of nodes correctly identified by approximate methods in Top-1% nodes.(2)
Top-5%-Hits: the fraction of nodes correctly identified in Top-5% nodes.(3)
Top-10%-Hits: the fraction of nodes correctly identified in Top-10% nodes.(4)
Inversion: normalized inversion number of estimated ranking with exact ranking as the standard. After computing the inversion number, we normalized it and mapped it to [0, 1]: inversion =1−2∗inv/N∗N−1, where N is the number of nodes and inv is the exact inversion number.(5)
Weightedtau: a node with ranka is mapped to weight 1/(a + 1) and an exchange between two nodes with rank a and b has weight 1/(a + 1) + 1/(b + 1). That is, top-ranked nodes have higher weights, which increase the impact of the exchanges between important nodes.(6)
10% GCC reduction (p10%): it represents how many nodes the method requires to remove to dismantle the network until GCC < 10% ∗ N. The normalized value p10% is mapped to [0, 1] and 1 means the method which needs the minimum number of nodes to get 10% GCC reduction.


## 2.4.2. Runtime

We conduct experiments on the same computer with four i7-6500U cores (2.50 GHz) and 16 GB RAM. We run each approximate method independently and recorded the exact runtime.


## 2.4.3. Trade-Offs

Considering six measures of accuracy, we normalized the runtime and plotted it with normalized measures to see which method can offer a nice trade-off. In order to analyze the results on different networks, we computed the average normalized runtime and measure values. To sum up, we use six measures to evaluate accuracy, and we also analyzed runtime and trade-offs. Besides, we set the naming schedule as approximation algorithm_parameter_k (e.g., RAND2_64_2 represents using RAND2 algorithm with number of pivots = 64 and k = 2).


## 3. Results

### 3.1. Networks in this Study

First, we generated 9 ER (Erdos–Renyi) graphs, 9 BA (Barabási-Albert) graphs, and 27 WS (Watts–Strogatz small-world) graphs with different sizes and parameters. Table2 provides an overview of our random networks and generator parameters. Figure 4 visualizes four selected random networks. On these random graphs, we performed sensitivity analysis of Top-1-node-identification for three selected methods in order to select reasonable parameters. In addition, we selected 48 real-world networks of different sizes and structures, covering a variety of domains, as obtained from http://networkrepository.com/networks.php:(i)
Social (4 networks): networks showing the social friendships between people. Nodes are persons and edges represent their connections.(ii)
Biological (5 networks): networks showing the interactions between elements in biological systems.(iii)
Brain (7 networks): networks representing functional connectivity in brains. We chose different brain networks of mouse, macaque, and fly.(iv)
Ecology (2 networks): networks showing the interactions between species.(v)
Economic (2 networks): networks representing interactions between interconnected economic agents.(vi)
Infrastructure (3 networks): networks consisting of interlinks between fundamental facilities.(vii)
Power (5 networks): networks showing the transmission of electric power.(viii)
Road (2 networks): networks representing road connectivity between intersections.(ix)
Technological (2 networks): networks consisting of the interlinks between technology systems.(x)
Web (5 networks): networks representing the hyperlinks between pages of the World Wide Web.(xi)
Email (2 networks): networks showing mail contacts between two addresses.(xii)
Retweet (7 networks): networks describing retweeting relationships on Twitter.(xiii)
Cheminformatics (2 networks): networks reflecting the chemical interactions of materials.Table 2
Overview of generated random network types.
ID
Name
Generator parameters
Naming scheme
ER
Erdos–Renyi
The number of nodesn ∈ {300, 700, 1000}The probability for edge creation pER ∈ {0.015, 0.02, 0.025}
ER_n_pER
BA
Barabási-Albert
The number of nodesn ∈ {300, 700, 1000}The number of edges to attach from a new node to existing nodes m ∈ {2, 4, 6}
BA_n_m
WS
Watts–Strogatz
The number of nodesn ∈ {300, 700, 1000}The number of nearest neighbors that each node is joined with (kWS) ∈ {3, 5, 7}The probability of rewiring each edge pWS ∈ {0.2, 0.5, 0.8}
WS_n_kWS_pWSFigure 4
Visualization of four random networks withN = 300. (a) ER_300_0.015. (b) BA_300_2. (c) WS_300_3_0.2. (d) WS_300_3_0.5.
(a)
(b)
(c)
(d)Table3 shows an overview of our 48 real-world datasets, including network properties.Table 3
Overview of the real-world datasets.
Category
Range of nodes
Range of edges
Range of density
Range of maximum degree
Social networks
[889, 12645]
[2914, 49132]
[0.000615, 0.008053]
[102, 4800]
Biological networks
[453, 3343]
[1948, 6437]
[0.001139, 0.019780]
[37, 523]
Brain networks
[29, 1770]
[44, 16089]
[0.003157, 0.712596]
[31, 927]
Ecology networks
[97, 128]
[1446, 2075]
[0.25529, 0.310567]
[90, 110]
Economic networks
[257, 1258]
[2375, 7513]
[0.009502, 0.072197]
[106, 206]
Infrastructure networks
[332, 4941]
[2126, 15645]
[0.00054, 0.038693]
[19, 242]
Power networks
[494, 5300]
[586, 8271]
[0.000589, 0.004812]
[9, 17]
Road networks
[1039, 2640]
[1305, 3302]
[0.000948, 0.00242]
[5, 10]
Technological networks
[2113, 10680]
[6632, 24316]
[0.000426, 0.002972]
[109, 205]
Web networks
[643, 12305]
[2280, 47606]
[0.000258, 0.011046]
[59, 199]
Email networks
[143, 1133]
[[623, 5451]
[0.0085, 0.061361]
[42, 71]
Retweet networks
[2280, 9631]
[2464, 10314]
[0.000211, 0.000948]
[267, 7655]
Cheminformatics networks
[123, 125]
[139, 141]]
[0.018194, 0.018526]
[5]


### 3.2. Sensitivity Analysis/Parameter Selection

In order to select reasonable parameters of approximation methods, we evaluated the quality of identification of the Top-1 node with each selected method by computing static betweenness with each method on our generated random networks. Figure5 reports the fraction of networks on which each competitor can correctly identify the Top-1 node.RAND2: Figure5 shows the results of identifying the Top-1 node on random networks regarding different number of sampled pivots. It can be seen that the quality (measured as ratio of correctly identified nodes) increases with the number of pivots and sampling with 512 pivots is the best. RAND2_64 can be chosen as a trade-off one and it correctly identifies over 70% WS networks and saves much time.RK: as Figure5 indicates, it can get the best quality when we set ϵ=0.07. However, it only identified 60% of all random graphs. As RK with ϵ=0.2 and 0.3 cannot identify Top-1 node in all ER networks, we chose ϵ=0.07 and 0.1.KPATH: the results of KPATH are shown in Figure5. The quality is the worst compared to RAND2 and RK. KPATH_0.2_4 and KPATH_0.2_8 are reasonable among all selected settings.Figure 5
Top-1-Hits of different static betweenness approximation techniques on random networks. (a) RAND2. (b) RK. (c) KPATH.
(a)
(b)
(c)With these results, we selected RAND2_512, RAND2_64, RK_0.07_0.1, RK_0.10_0.1, KPATH_0.2_4, and KPATH_0.2_8 for further analysis in the remaining part of the study.


### 3.3. Accuracy

Since the computation on real-world networks is expensive, we analyzed results on generated random graphs first, in order to select competitors and conduct further experiments on real-world networks. Figure6 presents the average measure values of 66 competitors. We can see that RAND2_512_1 offers the highest accuracy in general.Figure 6
Average measure values of 66 competitors on 45 random networks.Figure7 presents the distribution of 10% GCC reduction of 66 competitors. We can see that on 10% GCC reduction measure, which is closely related to dismantling problem, the quality of RAND2_64_1 is also good. Moreover, the accuracy of RAND2_64 is close to RAND2_512 with different k. Table 4 shows the measure values and runtime on a specific ER network. RAND2_64, RK_0.10_0.1, and KPATH_0.2_4 can save runtime compared to RAND2_512, RK_0.07_0.1, and KPATH_0.2_8. Considering the prohibitive computational costs on larger networks, we selected RAND2_64, RK_0.10_0.1, and KPATH_0.2_4 for further analysis on 48 real-world networks.Figure 7
Distribution of 10% GCC reduction of 66 competitors on 45 random networks.Table 4
Results on ER networks with 300 nodes with generator parameterp=0.02, using six approximation algorithms and setting k = 1.
Measure
RAND2_512
RAND2_64
RK_0.07_0.1
RK_0.10_0.1
KPATH_0.2_8
KPATH_0.2_4
Runtime (s)
39.7
22.9
28.5
23.7
8.1
4.2
Top-1%-Hits
0.75
0.75
0.75
0.25
0.75
0.75
Top-5%-Hits
0.75
0.75
0.81
0.69
0.88
0.81
Top-10%-Hits
0.90
0.87
0.81
0.81
0.77
0.67
Weightedtau
0.01
0.12
0.08
0.17
0.02
0.01
Inversion
0.78
0.81
0.82
0.80
0.84
0.84
p
10
%
0.97
0.97
0.94
0.94
0.83
0.69


#### 3.3.1. Real-World Networks

We ran experiments on 48 real-world networks and computed six measure values of accuracy. Figure8 presents the distribution of measure values. We can see that RAND2_64 with k = 1 is outstanding on all measures. Besides, when setting constant k values, the quality becomes worse as we increase the k value. On measure p10% (GCC 10% reduction), it is clear that the quality becomes worse from k = 1% to k = 20%. Besides, RAND2_64 and RK_0.10_0.1 with removing certain nodes with B≥ 0.5 can also offer good accuracy. Compared to RAND2_64 and RK_0.10_0.1, the quality of KPATH_0.2_4 is not good. We computed the average measure values on 48 real-world networks, and the results are shown in Figure 9: RAND2_64_1, RK_0.10_0.1_1, RAND2_64_0.5, and RK_0.10_0.1_0.5 are good.Figure 8
Distribution of measure values on 48 real-world networks.Figure 9
Average measure values of different competitors.


### 3.4. Runtime

The runtime of computing interactive betweenness depends on the size of the network, choices ofk, and selected approximation algorithms. We analyzed the runtime regarding different k values with the same approximation method. Besides, we evaluated the runtime of different approximation methods with the same k setting.


#### 3.4.1. Runtime regrading Differentk Settings

Figure10 plots the runtime (in seconds) of RAND2_64, RK_0.10_0.1 and KPATH_0.2_4 with the same k setting (i.e., k = certain nodes with B≥0.5) on different real-world networks with y-axis = runtime in seconds and x-axis = NlogN where N is the number of nodes in the network. We can see that Figure 10 shows that the time complexity is around ONlogN for these sparse real-world networks. Note that for dense networks, the runtime will be nearly ON2 theoretically. Moreover, the runtime of RAND2_64 is the highest, while KPATH_0.2_4 is the fastest among three approximation methods, but it does not offer a nice quality.Figure 10
Runtime regrading different approximation methods;x-axis is N∗logN, where N is the size of the network.


#### 3.4.2. Runtime regrading Different Approximation Methods

Figure11 shows the runtime of RK_0.10_0.1 with k from 1 to 16. We can see that the runtime increases as k decreases. If we choose smaller k, then fewer nodes are removed in each iteration, resulting in larger number of iterations and computational costs. Besides, doubling the k value will save 50% runtime when k ≥ 2. When k = 1, the runtime reaches its upper bound and is not doubled compared to k = 2.Figure 11
Runtime regrading differentk settings; x-axis is N∗logN, where N is the size of the network.To sum up, on sparse real-world networks, the actual runtime isONlogN from our results and has a linear relationship with k ≥ 2.


### 3.5. Speedup

In this section, we present the speedup of interactive betweenness approximation compared to the standard BETWI (exact interactive betweenness computation). Based on our experimental results of BETWI and other approximation methods conducted on the same computer, we computed the speedups on three ER networks with different sizes (N = 300, 400, 500, 600, 700, 800, 900, and 1000) but the same generator parameter p=0.02. Similar to our analysis of runtime, our evaluation on the speedups of interactive betweenness approximation sheds light on two aspects, the speedups of different betweenness approximation algorithms and the speedups with increasing k. Figure 12(a) shows the speedups of RAND2_512, RAND2_64, RK_0.07_0.1, RK_0.10_0.1, KPATH_0.2_4, and KPATH_0.2_8 with the same k setting. We can see that the speedup increases as the network becomes larger. As a fast algorithm, KPATH offers great speedups compared to RK and RAND2. Figure 12(b) presents the speedups with different k settings. Removing one node from GCC in each iteration induces low speedups, while doubling the k value approximately doubles the speedup.Figure 12
Speedups of different betweenness approximation algorithms withk = 4 (a) and speedups with increasing k using RK_0.10_0.1 (b).
(a)
(b)


### 3.6. Trade-Offs

From the results on quality and runtime, some competitors (e.g., RAND2_64_0.5) get high quality but need hours on the largest network. Several methods (e.g., KPATH_0.2_4 withk = 16) are quite fast but the quality is bad. In this section, we focus on the trade-offs of these selected competitors.


#### 3.6.1. Trade-Offs on Specific Networks

Figure13 presents trade-offs between quality (i.e., the values of six measures of accuracy) and speed (exact runtime). We used 3 colors to distinguish 3 approximation methods and 3 markers to label 3 typical k settings, including a faster one (k = 16), a slowest one (k = 1), and k = 4 as a trade-off. We can see that the RK_0.10_0.1 with k = 4 gets nice trade-offs on Top-1%-Hits, taking no more than 25% runtime to get high accuracy compared to the maximum runtime, while when we consider inversion measure, KPATH_0.2_4 with k = 1 is good. In addition, RAND2_64 with k = 4 also provides pleasurable trade-offs on both Top-1%-Hits and Weightedtau.Figure 13
Trade-offs on inf-power network with 4941 nodes.
(a)
(b)
(c)
(d)
(e)
(f)


#### 3.6.2. Average Trade-Offs

As there are orders of magnitude deviation between runtime on different networks, to analyze the trade-offs on 48 real-world networks, we normalized the runtime on each network with the slowest = 1 and the fastest = 0 and then we computed the average normalized runtime on 48 networks. Besides, we further normalized the measure values to map these values into [0, 1] on each network and computed the average normalized measure values. Figure14 shows the results. We used the same labels as Figure 13 and added legends of these competitors with average normalized runtime ≤0.5 and average normalized measure values ≥0.6. We can see that setting k in [2, 4, 1%, 0.5] can make good trade-offs with specific approximation methods.Figure 14
Trade-offs on 48 real-world networks.
(a)
(b)
(c)
(d)
(e)
(f)


## 3.1. Networks in this Study

First, we generated 9 ER (Erdos–Renyi) graphs, 9 BA (Barabási-Albert) graphs, and 27 WS (Watts–Strogatz small-world) graphs with different sizes and parameters. Table2 provides an overview of our random networks and generator parameters. Figure 4 visualizes four selected random networks. On these random graphs, we performed sensitivity analysis of Top-1-node-identification for three selected methods in order to select reasonable parameters. In addition, we selected 48 real-world networks of different sizes and structures, covering a variety of domains, as obtained from http://networkrepository.com/networks.php:(i)
Social (4 networks): networks showing the social friendships between people. Nodes are persons and edges represent their connections.(ii)
Biological (5 networks): networks showing the interactions between elements in biological systems.(iii)
Brain (7 networks): networks representing functional connectivity in brains. We chose different brain networks of mouse, macaque, and fly.(iv)
Ecology (2 networks): networks showing the interactions between species.(v)
Economic (2 networks): networks representing interactions between interconnected economic agents.(vi)
Infrastructure (3 networks): networks consisting of interlinks between fundamental facilities.(vii)
Power (5 networks): networks showing the transmission of electric power.(viii)
Road (2 networks): networks representing road connectivity between intersections.(ix)
Technological (2 networks): networks consisting of the interlinks between technology systems.(x)
Web (5 networks): networks representing the hyperlinks between pages of the World Wide Web.(xi)
Email (2 networks): networks showing mail contacts between two addresses.(xii)
Retweet (7 networks): networks describing retweeting relationships on Twitter.(xiii)
Cheminformatics (2 networks): networks reflecting the chemical interactions of materials.Table 2
Overview of generated random network types.
ID
Name
Generator parameters
Naming scheme
ER
Erdos–Renyi
The number of nodesn ∈ {300, 700, 1000}The probability for edge creation pER ∈ {0.015, 0.02, 0.025}
ER_n_pER
BA
Barabási-Albert
The number of nodesn ∈ {300, 700, 1000}The number of edges to attach from a new node to existing nodes m ∈ {2, 4, 6}
BA_n_m
WS
Watts–Strogatz
The number of nodesn ∈ {300, 700, 1000}The number of nearest neighbors that each node is joined with (kWS) ∈ {3, 5, 7}The probability of rewiring each edge pWS ∈ {0.2, 0.5, 0.8}
WS_n_kWS_pWSFigure 4
Visualization of four random networks withN = 300. (a) ER_300_0.015. (b) BA_300_2. (c) WS_300_3_0.2. (d) WS_300_3_0.5.
(a)
(b)
(c)
(d)Table3 shows an overview of our 48 real-world datasets, including network properties.Table 3
Overview of the real-world datasets.
Category
Range of nodes
Range of edges
Range of density
Range of maximum degree
Social networks
[889, 12645]
[2914, 49132]
[0.000615, 0.008053]
[102, 4800]
Biological networks
[453, 3343]
[1948, 6437]
[0.001139, 0.019780]
[37, 523]
Brain networks
[29, 1770]
[44, 16089]
[0.003157, 0.712596]
[31, 927]
Ecology networks
[97, 128]
[1446, 2075]
[0.25529, 0.310567]
[90, 110]
Economic networks
[257, 1258]
[2375, 7513]
[0.009502, 0.072197]
[106, 206]
Infrastructure networks
[332, 4941]
[2126, 15645]
[0.00054, 0.038693]
[19, 242]
Power networks
[494, 5300]
[586, 8271]
[0.000589, 0.004812]
[9, 17]
Road networks
[1039, 2640]
[1305, 3302]
[0.000948, 0.00242]
[5, 10]
Technological networks
[2113, 10680]
[6632, 24316]
[0.000426, 0.002972]
[109, 205]
Web networks
[643, 12305]
[2280, 47606]
[0.000258, 0.011046]
[59, 199]
Email networks
[143, 1133]
[[623, 5451]
[0.0085, 0.061361]
[42, 71]
Retweet networks
[2280, 9631]
[2464, 10314]
[0.000211, 0.000948]
[267, 7655]
Cheminformatics networks
[123, 125]
[139, 141]]
[0.018194, 0.018526]
[5]


## 3.2. Sensitivity Analysis/Parameter Selection

In order to select reasonable parameters of approximation methods, we evaluated the quality of identification of the Top-1 node with each selected method by computing static betweenness with each method on our generated random networks. Figure5 reports the fraction of networks on which each competitor can correctly identify the Top-1 node.RAND2: Figure5 shows the results of identifying the Top-1 node on random networks regarding different number of sampled pivots. It can be seen that the quality (measured as ratio of correctly identified nodes) increases with the number of pivots and sampling with 512 pivots is the best. RAND2_64 can be chosen as a trade-off one and it correctly identifies over 70% WS networks and saves much time.RK: as Figure5 indicates, it can get the best quality when we set ϵ=0.07. However, it only identified 60% of all random graphs. As RK with ϵ=0.2 and 0.3 cannot identify Top-1 node in all ER networks, we chose ϵ=0.07 and 0.1.KPATH: the results of KPATH are shown in Figure5. The quality is the worst compared to RAND2 and RK. KPATH_0.2_4 and KPATH_0.2_8 are reasonable among all selected settings.Figure 5
Top-1-Hits of different static betweenness approximation techniques on random networks. (a) RAND2. (b) RK. (c) KPATH.
(a)
(b)
(c)With these results, we selected RAND2_512, RAND2_64, RK_0.07_0.1, RK_0.10_0.1, KPATH_0.2_4, and KPATH_0.2_8 for further analysis in the remaining part of the study.


## 3.3. Accuracy

Since the computation on real-world networks is expensive, we analyzed results on generated random graphs first, in order to select competitors and conduct further experiments on real-world networks. Figure6 presents the average measure values of 66 competitors. We can see that RAND2_512_1 offers the highest accuracy in general.Figure 6
Average measure values of 66 competitors on 45 random networks.Figure7 presents the distribution of 10% GCC reduction of 66 competitors. We can see that on 10% GCC reduction measure, which is closely related to dismantling problem, the quality of RAND2_64_1 is also good. Moreover, the accuracy of RAND2_64 is close to RAND2_512 with different k. Table 4 shows the measure values and runtime on a specific ER network. RAND2_64, RK_0.10_0.1, and KPATH_0.2_4 can save runtime compared to RAND2_512, RK_0.07_0.1, and KPATH_0.2_8. Considering the prohibitive computational costs on larger networks, we selected RAND2_64, RK_0.10_0.1, and KPATH_0.2_4 for further analysis on 48 real-world networks.Figure 7
Distribution of 10% GCC reduction of 66 competitors on 45 random networks.Table 4
Results on ER networks with 300 nodes with generator parameterp=0.02, using six approximation algorithms and setting k = 1.
Measure
RAND2_512
RAND2_64
RK_0.07_0.1
RK_0.10_0.1
KPATH_0.2_8
KPATH_0.2_4
Runtime (s)
39.7
22.9
28.5
23.7
8.1
4.2
Top-1%-Hits
0.75
0.75
0.75
0.25
0.75
0.75
Top-5%-Hits
0.75
0.75
0.81
0.69
0.88
0.81
Top-10%-Hits
0.90
0.87
0.81
0.81
0.77
0.67
Weightedtau
0.01
0.12
0.08
0.17
0.02
0.01
Inversion
0.78
0.81
0.82
0.80
0.84
0.84
p
10
%
0.97
0.97
0.94
0.94
0.83
0.69


### 3.3.1. Real-World Networks

We ran experiments on 48 real-world networks and computed six measure values of accuracy. Figure8 presents the distribution of measure values. We can see that RAND2_64 with k = 1 is outstanding on all measures. Besides, when setting constant k values, the quality becomes worse as we increase the k value. On measure p10% (GCC 10% reduction), it is clear that the quality becomes worse from k = 1% to k = 20%. Besides, RAND2_64 and RK_0.10_0.1 with removing certain nodes with B≥ 0.5 can also offer good accuracy. Compared to RAND2_64 and RK_0.10_0.1, the quality of KPATH_0.2_4 is not good. We computed the average measure values on 48 real-world networks, and the results are shown in Figure 9: RAND2_64_1, RK_0.10_0.1_1, RAND2_64_0.5, and RK_0.10_0.1_0.5 are good.Figure 8
Distribution of measure values on 48 real-world networks.Figure 9
Average measure values of different competitors.


## 3.3.1. Real-World Networks

We ran experiments on 48 real-world networks and computed six measure values of accuracy. Figure8 presents the distribution of measure values. We can see that RAND2_64 with k = 1 is outstanding on all measures. Besides, when setting constant k values, the quality becomes worse as we increase the k value. On measure p10% (GCC 10% reduction), it is clear that the quality becomes worse from k = 1% to k = 20%. Besides, RAND2_64 and RK_0.10_0.1 with removing certain nodes with B≥ 0.5 can also offer good accuracy. Compared to RAND2_64 and RK_0.10_0.1, the quality of KPATH_0.2_4 is not good. We computed the average measure values on 48 real-world networks, and the results are shown in Figure 9: RAND2_64_1, RK_0.10_0.1_1, RAND2_64_0.5, and RK_0.10_0.1_0.5 are good.Figure 8
Distribution of measure values on 48 real-world networks.Figure 9
Average measure values of different competitors.


## 3.4. Runtime

The runtime of computing interactive betweenness depends on the size of the network, choices ofk, and selected approximation algorithms. We analyzed the runtime regarding different k values with the same approximation method. Besides, we evaluated the runtime of different approximation methods with the same k setting.


### 3.4.1. Runtime regrading Differentk Settings

Figure10 plots the runtime (in seconds) of RAND2_64, RK_0.10_0.1 and KPATH_0.2_4 with the same k setting (i.e., k = certain nodes with B≥0.5) on different real-world networks with y-axis = runtime in seconds and x-axis = NlogN where N is the number of nodes in the network. We can see that Figure 10 shows that the time complexity is around ONlogN for these sparse real-world networks. Note that for dense networks, the runtime will be nearly ON2 theoretically. Moreover, the runtime of RAND2_64 is the highest, while KPATH_0.2_4 is the fastest among three approximation methods, but it does not offer a nice quality.Figure 10
Runtime regrading different approximation methods;x-axis is N∗logN, where N is the size of the network.


### 3.4.2. Runtime regrading Different Approximation Methods

Figure11 shows the runtime of RK_0.10_0.1 with k from 1 to 16. We can see that the runtime increases as k decreases. If we choose smaller k, then fewer nodes are removed in each iteration, resulting in larger number of iterations and computational costs. Besides, doubling the k value will save 50% runtime when k ≥ 2. When k = 1, the runtime reaches its upper bound and is not doubled compared to k = 2.Figure 11
Runtime regrading differentk settings; x-axis is N∗logN, where N is the size of the network.To sum up, on sparse real-world networks, the actual runtime isONlogN from our results and has a linear relationship with k ≥ 2.


## 3.4.1. Runtime regrading Differentk Settings

Figure10 plots the runtime (in seconds) of RAND2_64, RK_0.10_0.1 and KPATH_0.2_4 with the same k setting (i.e., k = certain nodes with B≥0.5) on different real-world networks with y-axis = runtime in seconds and x-axis = NlogN where N is the number of nodes in the network. We can see that Figure 10 shows that the time complexity is around ONlogN for these sparse real-world networks. Note that for dense networks, the runtime will be nearly ON2 theoretically. Moreover, the runtime of RAND2_64 is the highest, while KPATH_0.2_4 is the fastest among three approximation methods, but it does not offer a nice quality.Figure 10
Runtime regrading different approximation methods;x-axis is N∗logN, where N is the size of the network.


## 3.4.2. Runtime regrading Different Approximation Methods

Figure11 shows the runtime of RK_0.10_0.1 with k from 1 to 16. We can see that the runtime increases as k decreases. If we choose smaller k, then fewer nodes are removed in each iteration, resulting in larger number of iterations and computational costs. Besides, doubling the k value will save 50% runtime when k ≥ 2. When k = 1, the runtime reaches its upper bound and is not doubled compared to k = 2.Figure 11
Runtime regrading differentk settings; x-axis is N∗logN, where N is the size of the network.To sum up, on sparse real-world networks, the actual runtime isONlogN from our results and has a linear relationship with k ≥ 2.


## 3.5. Speedup

In this section, we present the speedup of interactive betweenness approximation compared to the standard BETWI (exact interactive betweenness computation). Based on our experimental results of BETWI and other approximation methods conducted on the same computer, we computed the speedups on three ER networks with different sizes (N = 300, 400, 500, 600, 700, 800, 900, and 1000) but the same generator parameter p=0.02. Similar to our analysis of runtime, our evaluation on the speedups of interactive betweenness approximation sheds light on two aspects, the speedups of different betweenness approximation algorithms and the speedups with increasing k. Figure 12(a) shows the speedups of RAND2_512, RAND2_64, RK_0.07_0.1, RK_0.10_0.1, KPATH_0.2_4, and KPATH_0.2_8 with the same k setting. We can see that the speedup increases as the network becomes larger. As a fast algorithm, KPATH offers great speedups compared to RK and RAND2. Figure 12(b) presents the speedups with different k settings. Removing one node from GCC in each iteration induces low speedups, while doubling the k value approximately doubles the speedup.Figure 12
Speedups of different betweenness approximation algorithms withk = 4 (a) and speedups with increasing k using RK_0.10_0.1 (b).
(a)
(b)


## 3.6. Trade-Offs

From the results on quality and runtime, some competitors (e.g., RAND2_64_0.5) get high quality but need hours on the largest network. Several methods (e.g., KPATH_0.2_4 withk = 16) are quite fast but the quality is bad. In this section, we focus on the trade-offs of these selected competitors.


### 3.6.1. Trade-Offs on Specific Networks

Figure13 presents trade-offs between quality (i.e., the values of six measures of accuracy) and speed (exact runtime). We used 3 colors to distinguish 3 approximation methods and 3 markers to label 3 typical k settings, including a faster one (k = 16), a slowest one (k = 1), and k = 4 as a trade-off. We can see that the RK_0.10_0.1 with k = 4 gets nice trade-offs on Top-1%-Hits, taking no more than 25% runtime to get high accuracy compared to the maximum runtime, while when we consider inversion measure, KPATH_0.2_4 with k = 1 is good. In addition, RAND2_64 with k = 4 also provides pleasurable trade-offs on both Top-1%-Hits and Weightedtau.Figure 13
Trade-offs on inf-power network with 4941 nodes.
(a)
(b)
(c)
(d)
(e)
(f)


### 3.6.2. Average Trade-Offs

As there are orders of magnitude deviation between runtime on different networks, to analyze the trade-offs on 48 real-world networks, we normalized the runtime on each network with the slowest = 1 and the fastest = 0 and then we computed the average normalized runtime on 48 networks. Besides, we further normalized the measure values to map these values into [0, 1] on each network and computed the average normalized measure values. Figure14 shows the results. We used the same labels as Figure 13 and added legends of these competitors with average normalized runtime ≤0.5 and average normalized measure values ≥0.6. We can see that setting k in [2, 4, 1%, 0.5] can make good trade-offs with specific approximation methods.Figure 14
Trade-offs on 48 real-world networks.
(a)
(b)
(c)
(d)
(e)
(f)


## 3.6.1. Trade-Offs on Specific Networks

Figure13 presents trade-offs between quality (i.e., the values of six measures of accuracy) and speed (exact runtime). We used 3 colors to distinguish 3 approximation methods and 3 markers to label 3 typical k settings, including a faster one (k = 16), a slowest one (k = 1), and k = 4 as a trade-off. We can see that the RK_0.10_0.1 with k = 4 gets nice trade-offs on Top-1%-Hits, taking no more than 25% runtime to get high accuracy compared to the maximum runtime, while when we consider inversion measure, KPATH_0.2_4 with k = 1 is good. In addition, RAND2_64 with k = 4 also provides pleasurable trade-offs on both Top-1%-Hits and Weightedtau.Figure 13
Trade-offs on inf-power network with 4941 nodes.
(a)
(b)
(c)
(d)
(e)
(f)


## 3.6.2. Average Trade-Offs

As there are orders of magnitude deviation between runtime on different networks, to analyze the trade-offs on 48 real-world networks, we normalized the runtime on each network with the slowest = 1 and the fastest = 0 and then we computed the average normalized runtime on 48 networks. Besides, we further normalized the measure values to map these values into [0, 1] on each network and computed the average normalized measure values. Figure14 shows the results. We used the same labels as Figure 13 and added legends of these competitors with average normalized runtime ≤0.5 and average normalized measure values ≥0.6. We can see that setting k in [2, 4, 1%, 0.5] can make good trade-offs with specific approximation methods.Figure 14
Trade-offs on 48 real-world networks.
(a)
(b)
(c)
(d)
(e)
(f)


## 4. Conclusions

Betweenness centrality is a widely used measure of node importance, which counts the number of shortest paths a node appears in a network. However, if one node in the network is being attacked or loses its functionality, the betweenness values of other nodes will change. That is, all betweenness values need to be recomputed, in order to update the actual node importance. Recent research suggests that, on network dismantling problem, interactively removing one node with the highest betweenness outperforms removing nodes based on ranking obtained by one time betweenness computation. However, the interactive betweenness computation requires static betweenness recomputation on current GCC after each node removal and it is significantly more computationally expensive (an order of magnitude) compared to static approaches.In this paper, we systematically investigated approximation of interactive betweenness centrality. We proposed a framework for interactive betweenness estimation withk-batch removal. Our framework consists of a set of static betweenness approximation algorithms with various parameter settings for identifying top nodes with high betweenness and selections of how many nodes to be removed in each iteration. In other words, we not only analyzed the performance of removing one top node but also evaluated the removal of a batch of nodes. As the computation of interactive betweenness is more expensive than the computation of static betweenness, we focus on choosing approximation methods with parameter settings and k values (the number of nodes to be removed in each iteration) which can offer high quality and also a nice trade-off between accuracy and speed. To ensure that our datasets cover different network structures, we generated 45 random networks, including ER, WS, and BA networks, and selected 48 real-world networks with distinct sizes from different fields. We devised six measures to evaluate accuracy considering the identification of important node, the similarity of rankings, and the effects on GCC reduction.To make preliminary selections of suitable parameter settings, we conducted sensitivity analysis of static betweenness approximation algorithms and evaluated the quality of identification of Top-1 node on random networks. We selected six approximation methods, consisting of RAND2_64, RAND2_512, RK_0.07_0.1, RK_0.10_0.1, KPATH_0.2_4, and KPATH_0.2_8. As fork settings, based on the results of 50% GCC reduction, we found that many networks can be dismantled with a small fraction of nodes and we chose 11 different k settings (k in [1, 2, 4, 8, 16, 1%, 5%, 10%, 20%, AS, 0.5]). We ran tests with 66 competitors (six approximation algorithms with 11 k settings) on random networks to further select competitors. Based on the results on random networks, we chose RAND2_64, RK_0.10_0.1 and KPATH_0.2_4 with 11 k settings and conducted experiments on larger real-world networks. We found that RAND2_64_1, RAND2_64_0.5, RK_0.10_0.1_1, and RK_0.10_0.1_0.5 offer high accuracy. Besides, we analyzed the runtime regarding different approximation algorithms and k settings. Our analysis on different approximation methods with the same k reveals that RAND2_64 is the slowest and KPATH_0.2_4 is the fastest competitor. Moreover, we also found that doubling k values will get 50% runtime reduction for k≥ 2 and the runtime reaches its upper bound with k = 1 (shown by Figure 11). Our analysis indicates that RAND2_64 and RK_0.10_0.1 with k = 2, 4, 1% and 0.5 provide a nice trade-off between accuracy and speed..In synthesis, we have proposed a novel framework for interactive betweenness approximation. We systematically evaluated the selections of approximation algorithms with various parameter settings and the choices of different batch removals from three aspects: accuracy, runtime, and trade-offs between them. Our work contributes to the analysis of complex network phenomena, with a particular focus on obtaining scalable techniques. Future work could investigate the interactive approximate computation of other network centrality measures.



---

*Source: 4046027-2020-02-27.xml*