Estimated Distance Limited Betweenness Centrality Based on Estimated Betweenness and Approximate Betweenness Algorithms

Given a graph G=(V,E), betweenness value of a vertex v∈V is defined by the sum over all s,t pair dependency (equation (1)). Pair dependency is ${\delta }_{st}\left[v\right]=\frac{{\sigma }_{st}\left[v\right]}{{\sigma }_{st}}$ the ratio of the number of the shortest paths between s and t which includes v(σ_st[v]) to the number of the shortest paths between s and (σ_st). BC exacts how much information is flowing through a node if information travels in shortest paths.

Brandes’ algorithm finds an exact betweenness value by dynamic programming technique to cleverly update pair dependency after each single source shortest path runs. We will refer to this algorithm [10] as BC from now on. While multi-path single source shortest path algorithm from s node is running, it stores predecessor set π_s [v] and σ_s [v] the number of shortest paths from s to v for every node v. Then, δ_s [v] the pair dependency of node v starting from s node is π_s [v]=[Σ_t∈vδ_st[v]. This can be further expanded by introducing vertex and edge combination as shown in equation 2 where δ_st [v,(v,w)] denotes the dependency of the paths taking (v,w) edge from v on all s–t shortest paths. Total dependency of v starting from s node (δ_s [v]) can be summed over δ_st [v,(v,w)] where w is the node whose predecessor is v on s–t shortest paths. In other words, all the shortest paths where one visits v and then w node are included in δ_s [v].

The dependency of v node and edge (v,w), δ_st [v,(v,w)], can be written as the relation shown in equation (3). This relation is trivial when t=w since σ_st number of s–t shortest paths is equal to σ_sw, of which exactly σ_sv of them passes through v and uses (v,w) edge to reach w node.

Now for t≠w case, number of the s–t shortest paths which include w node is equal to σ_st[w]=σ_swσ_wt. Because all the s–w shortest paths can be merged with w–t shortest paths to create s–t shortest paths if w is on s–t shortest path. Number of w–t shortest path becomes σ_wt=σ_st[w]/σ_sw from previous definition. Then, number of shortest paths passing through v and taking (v,w) edge is the multiplication of σ_sv and σ_wt and replacing σ_wt with previous definition gives following equation.

We divide this equation by σ_st to get δ_st[v,(v,w)] dependency (equation(3)).

Now, if we use the system of equations (equation (3)) in equation (2) which finds dependency of v node starting from s source node, we get the following equation.

It can be seen from the equation that δ_s [v] is recurrent. So the dynamic programming technique can be applied. We can process this recurrence starting from the nodes furthest from the source. Iterating over all s ∈ V to add up δ_s [v] gives betweenness centrality in O(nm) complexity on unweighted graph.

Estimated betweenness (e-BC) algorithm [13] is similar to BC but instead of calling SSSP from every node, it samples r number of vertices and calls SSSP algorithm from each of the sampled vertices. So, we have partial dependencies from r SSSP calls. In order to extrapolate this information, current betweenness value of each v node is multiplied by 2n/r. This algorithm is known to produce good approximation result although there is no theoretical error estimation in the paper. Its time complexity is O(rm) for unweighted graphs and O(rm+nrlog n) for weighted graphs.

Approximate betweenness (a-BC) algorithm [14] samples paths unlike e-BC. It determines sampling size r from algorithm parameters and diameter of a given graph. Then, it chooses u and v nodes randomly and runs SSSP algorithm from u to v. For each sample u and v, it samples a path with weight according to number of shortest paths running through each node on u–v shortest paths. Each node on the sampled path receives 1/r value added to its BC. Unlike e-BC, estimated betweenness values of a-BC has theoretical bound epsilon (deviations are within epsilon with probability 1–δ). Its time complexity is O(rn) for unweighted graphs and O(rm+nrlog n) for weighted graphs. Its running time is the same as e-BC but it runs slower than e-BC because it chooses larger sample size to achieve a theoretical bound.

k-BC algorithm [7] puts distance limit on shortest paths. k-BC is used in new types of problems like DCNP and some real-world cases. Also, it can be an effective estimated betweenness measurement. Distance limit is a hop distance for unweighted graphs. Graph traversal is stopped when hop distance reaches k in BFS algorithm. Time complexity of BFS becomes O(d^k) where d is branch factor and k is distance limit. Distance limit k=3 is used in distance limited problems like DCNP making single BFS call a constant when branch factor is small [21]. Distance is limited by range for weighted graph. We can stop Dijkstra’s algorithm once the distance of the current minimum exceeds the range limit. K-BC alone is able to reduce running time drastically when graph is sparse which is the case for real world instances.

BC and k-BC values are illustrated on a simple graph in Fig. 1(a) and Fig. 1(b) (k=2 is used) respectively. Let’s see how BC value of node 2 is calculated. First, BFS from node 1 is called. Then, starting from the furthest node which is 5, pair dependencies are calculated. Ratio $\frac{\sigma \left[2\right]}{\sigma \left[5\right]}\left(1+\delta \left[5\right]\right)=\frac{1}{1}\left(1+0\right)=\frac{1}{1}$ is added to the dependency of predecessor 2. In the same way, $\frac{1}{2}$ is added to the dependency of predecessor 2 when node 4 is processed next. Because there are two shortest paths from 1 to 4 and and only one of them passes through 2. Then, there is no other nodes from source 1 to contribute to node 2. When BFS is called from 3, the path from 3 to 5 adds $\frac{2}{2}=1$. When BFS is called from 4, the paths from 4 to 5 and 4 to 1 add 1 and $\frac{1}{2}$ respectively. The paths from 5 to 1, 5 to 4 and 5 to 3 add 1, 1, and $\frac{2}{2}=1$ respectively. Total of these dependencies sum up 7. K-BC is calculated in the same way but only the paths with length less than or equal to k=2 is considered. Therefore, k-BC value of node 2 consists of the dependencies from the paths 1 to 5, 5 to 1, 1 to 4, 4 to 1, 4 to 5 and 5 to 4.

Fig. 1. BC and k-BC values of the graph are shown in extended label. BC is shown on the left (a) and k-BC is shown on the right (b). k = 2 is used here.

Download Original Figure

We created estimated k-betweenness algorithm (ek-BC) by combining e-BC with k-BC. We replaced SSSP algorithm in e-BC with distance limited version. Pseudo code of ek-BC is shown in Algorithm 1. It takes G=(V,E) graph, r sample size and k distance bound. First, it initializes BC array to store betweenness values for all vertices (lines 1–2). Then, it samples r vertices from V randomly. For each sampled vertex s in V, it fills dependency array with zeros and calls multipath SSSP limited by k which returns S explored vertices sorted by their distance from s node, σ number of shortest paths passing through a vertex and predecessor array. Predecessor array is an array of arrays since each node can have multiple predecessors for storing multiple shortest paths. The vertices are processed starting from the furthest vertex from s node. For each u node, its dependency contribution to the predecessor nodes is calculated and added to the corresponding predecessor (lines 13–14). If u node is not s node, its dependency starting from s node is finalized and added to BC[u] (lines 15–16). Finally, BC calculation is scaled by multiplying each BC value by 2n/r (line 18).

Approximate k-betweenness (ak-BC) algorithm is created by combining k-BC with a-BC (Algorithm 2). First, the diameter of a given graph is estimated to calculate the sample size needed. Given ∨ and δ parameters, it calculates number of samples need to achieve the bound which states that the deviation of approximate betweenness value is within ∨ with probability 1–δ. Then, it initializes BC array to zero. For each of the r samples, u and v nodes are selected randomly and multipath SSSP limited by k is called to find all the shortest paths between u and v (lines 6–7). Then, it selects a single path among the shortest paths with weighted probability (lines 9–18). Selection process starts with v endpoint and next intermediate vertex (predecessor of the current vertex) is chosen by a weighted random choice (lines 12–15). The weight assigned to each predecessor depends on number of paths passing through it. Higher the number of shortest paths passing through a node is, the more likely it is for the node to be chosen. If the chosen vertex is not an endpoint, its betweenness value is increased by 1/r (lines 17–18).

Time complexity of ak-BC and ek-BC depends on the sample size and SSSP algorithm used. It is shown that distance limited BFS call takes O(d^k) time and it becomes a constant when branching factor d is small [21]. So, time complexity of both algorithms is O(rd^k) for unweighted graph. As for weighted graph, it’s difficult to draw time complexity because it depends on the search space of range limited Dijktra’s algorithm. But, it is likely to be small if the range used is an average of the shortest path distances within some small hop distance [16].

Dataset consists of 7 real world networks (Table 1). We took most difficult (largest) networks used in [13] i.e. US patent network, co-paper Citeseer network, co-paper DBLP network and world wide web graph in addition to other well-known networks such as Twitter and Amazon co-purchasing network [18]. In order to see the performance of distance limited versions on a weighted graph, days.net network used in [19] is taken.

Twitter is a social network created by crawling from public resources where nodes are profiles and circles in Twitter platform and edges represent friendship and follow status among the vertices. Amazon is a copurchasing network on their online shopping platform where vertices represent products and an edge between two vertices means that they are bought together frequently. US patent network is largest among the others where vertex is a patent and there is an edge between two patents if the one cites the other. Co-paper Citeseer and co-paper DBLP networks are based on the data generated from Citeseer and DBLP networks respectively where nodes are papers and an edge between them means that two papers share an author. World wide web graph is formed by link connection between web sites. Days.net, called Reuters terror news network (downloaded from Pajek datasets), contains word relation data collected from Reuters news for 66 consecutive days after tragic September 11 incident. The vertices are words and weighted edges between them mean that two words were present in one sentence while weight represents their frequency. We converted every w_i edge weight to W_max + 1 – w_i where W_max = max(w_i) so that shortest paths pass through words which used most frequently. BC gives interesting information and used for data analysis. It is able to detect influential people in circles on social and collaboration networks such as Twitter. For Amazon network, BC is used to predict sales-rank of the products [22].

We run a single thread instance of each algorithm on Twitter and Amazon datasets and measured their running times in seconds using perf_counter method of Python time module. Their running times are compared against running time of BC to see relative speed gain empirically. Running time of the algorithms are shown in Table 2. Ratio column shows relative speed gain which is the running time of BC divided by the running time of current algorithm. We considered only Twitter and Amazon network for simplicity (It takes weeks to calculate exact betweenness of larger graphs). BC is the slowest of them – 1.9 hours and 18.3 hours for Twitter and Amazon networks respectively because it finds exact BC values. E-BC runs 22 and 48.7 times faster whereas a-BC runs 0.7 and 2.4 times faster than BC. A-BC runs slower than exact BC on Twitter showing that its sample size was bigger than number of nodes. Distance limited algorithms run faster on larger and sparser graph i.e Amazon. k-BC was faster than e-BC and a-BC on Amazon. Ek-BC (k=3) gained 18 and 28.7 times faster compared to k-BC on both networks.

The algorithms show predictable behavior when effect of distance limit on running time is studied (Fig. 2). We used Twitter network whose diameter is 7. In the figure, running time of BC, e-BC and a-BC are constant as they are not distance limited. But we can see their running time differences (gaps). Running time of distance limited versions are closing in to their original algorithms at k=4 meaning that k=4 is already sufficient and covers most of the network. Since then, running time is around the same up and down little bit to their original running time. Running time fluctuation shows their random sampling nature. Number of paths in sampled nodes are larger than average and sometimes they are fewer. As we can see even at k=7 which is the diameter, the running time of ek-BC and ak-BC are faster than their original algorithms. When k increases, running time of distance limited algorithms are almost the same as their original versions.

Fig. 2. Running time over k distance limit.

Download Original Figure

Relative speed-ups gained by using ek-BC and ak-BC compared to k-BC are shown in Table 3. Ek-BC was 17.9–438.9 fold faster than k-BC. Both versions run faster when k=3 as predicted and speed-up increases as network grows larger. Speed-up gained by ak-BC is small compared to ek-BC. It runs 1–24.4 times faster than k-BC. On the other hand, ek-BC was at least 13 times faster than others. Estimated versions are faster because they have the best of the two worlds – distance limitation and estimation. Estimated algorithm halts when the distance limit is reached making the inner loop of the algorithms run faster while not causing any overhead.

Solution quality of proposed algorithms is studied in this section. BC values produced by e-BC, a-BC, ek-BC and ak-BC are compared against outputs of BC and k-BC using spearman’s correlation coefficient and Euclidean distance to see the solution compatibility with the original algorithms. Normalized betweenness values of n nodes are converted into n-dimensional vector in order to calculate euclidean distance. Also, we measured how many of top ranking L nodes of these algorithms are contained in the set containing top ranking 2L nodes of BC. Sizes of L are 10 and $\sqrt{n}$ in this experiment.

Euclidean distances of all the algorithms to BC and k-BC are calculated on Twitter network using different k distances (Fig. 3). All the algorithms followed predicted behavior meaning that their solution quality is converging to their original algorithms when k increases. In Figure 2a, k-BC’s euclidean distance is 0 at k=7 which means there is no difference between k-BC and BC at this point. Because diameter of the graph is 7 and k-BC is distanced version of BC. Euclidean distances of e-BC and a-BC are plotted as horizontal lines since they don’t depend on k parameter and these distances represent their algorithmic limit. Their distance limited versions were started far from their original version and gets closer as k increases. By the time k=6, ek-BC and ak-BC produce the same output as e-BC and a-BC. It is seen from the distance that ak-BC and aBC perform little better than e-BC and ek-BC on this dataset. The fact that distance limited versions are distanced a bit from BC at the beginning could mean that they represent different information at the beginning. This information fades away and they become like BC as k increases.

Fig. 3. quality change over k distance limit. Figure (a) shows Euclidean distance between BC and comparing algorithms. Figure (b) shows Euclidean distance between k-BC and comparing algorithms.

Download Original Figure

Fig. 3(b) shows Euclidean distance to k-BC. E-BC and a-BC look like getting closer to k-BC though they are not distance limited. This pattern is observed because k-BC changes to be closer to BC which is what they are approximate. On the other hand, ek-BC and ak-BC start very close to k-BC and get closer to their respective algorithms as k increases. This suggests that distance limited versions of the estimated algorithms are able to approximate k-BC. As k increases, they get close to their algorithmic limit which is estimating BC getting little distanced from k-BC while k-BC approaches to BC.

Solution closeness of ek-BC and ak-BC to k-BC is shown in Tables 4 and Table 5 using 4 different methods mentioned before. Tables show that spearman’s correlation coefficient is high for ek-BC for both k=3 and k=4. This means that its ranking is very close to the ranking of k-BC. Top-L columns confirm this result as we can see top 10 nodes of ek-BC are all in top-20 nodes of k-BC except Twitter and Amazon at k=3 where it misses only one node. When $L=\sqrt{n}$, ranking looks little bit off from k-BC but ek-BC was able to find most of them (k=3). This number improves when k=4 getting closer to k-BC which is our objective. For ak-BC, spearman’s correlation is low but it ranks top-10 and top-$\sqrt{n}$ well for Twitter, co-paper Citeseers, co-paper DBLP and world wide web graphs. It probably needs more sampling to work through larger graphs. For Euclidean distance, ek-BC is better than ak-BC. We can observe that Euclidean distance grows larger and node ranking gets better as k increases due to the effect we observed in Fig. 3.

Centering Resonance Analysis used betweenness centrality [20]. We used our proposed algorithms on Reuters dataset. Then, we run BC, k-BC, ek-BC and ak-BC on the data and captured top 6 words with highest BC value (Table 6). In this case, range limited algorithms (k=1,100 is used) produced reasonable answers when correct range is given since increasing range means that more sentences are traversed making it difficult to grasp the main theme of the news. k-BC is able to find all the attack sites and cities while BC mixes up cities with uninformative word like people. Proposed ek-BC and ak-BC algorithms produced exact same results as k-BC in much shorter time.