Path Merging Based Betweenness Centrality Algorithm in Delay Tolerant Networks
Zhigao Zheng, Bo Du, Chen Zhao, Peichen Xie
Abstract
Delay Tolerant Network (DTN) is a widely used network in computer network and wireless network, there are no permanent end-to-end connections between source and destination nodes (vertices). Betweenness centrality (BC) is used to find the key nodes (vertices) of DTNs, and there are kinds of implementations of the BC algorithm for DTNs. However, most recent algorithms in BC computation suffer from the problem of high auxiliary memory consumption. To reduce BC computing’s memory consumption, we propose a path-merging-based algorithm called Galliot to calculate the BC values using GPU, which aims to minimize the on-board memory consumption and enable the BC computation of large-scale graphs on GPU. The proposed algorithm requires <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(n)$ </tex-math></inline-formula> space and runs in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {O}(mn)$ </tex-math></inline-formula> time on unweighted graphs. We present the theoretical principle for the proposed path merging method. Moreover, we propose a locality-oriented policy to maintain and update the worklist to improve GPU data locality. In addition, we conducted extensive experiments on NVIDIA GPUs to show the performance of Galliot. The results show that Galliot can process the larger graphs, which have <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$11.32\times $ </tex-math></inline-formula> more vertices and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$5.67\times $ </tex-math></inline-formula> more edges than the graphs that recent works can process. Moreover, Galliot can achieve up to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$38.77\times $ </tex-math></inline-formula> speedup over the existing methods.