Yin Siyuan, Hu Yanmei, Ren Yuchun
College of Computer and Cyber Security, Chengdu University of Technology, Chengdu, China.
Math Biosci Eng. 2022 Jan 10;19(3):2700-2719. doi: 10.3934/mbe.2022123.
Many systems in real world can be represented as network, and network analysis can help us understand these systems. Node centrality is an important problem and has attracted a lot of attention in the field of network analysis. As the rapid development of information technology, the scale of network data is rapidly increasing. However, node centrality computation in large-scale networks is time consuming. Parallel computing is an alternative to speed up the computation of node centrality. GPU, which has been a core component of modern computer, can make a large number of core tasks work in parallel and has the ability of big data processing, and has been widely used to accelerate computing. Therefore, according to the parallel characteristic of GPU, we design the parallel algorithms to compute three widely used node centralities, i.e., closeness centrality, betweenness centrality and PageRank centrality. Firstly, we classify the three node centralities into two groups according to their definitions; secondly, we design the parallel algorithms by mapping the centrality computation of different nodes into different blocks or threads in GPU; thirdly, we analyze the correlations between different centralities in several networks, benefited from the designed parallel algorithms. Experimental results show that the parallel algorithms designed in this paper can speed up the computation of node centrality in large-scale networks, and the closeness centrality and the betweenness centrality are weakly correlated, although both of them are based on the shortest path.
现实世界中的许多系统都可以表示为网络，而网络分析有助于我们理解这些系统。节点中心性是一个重要问题，在网络分析领域引起了广泛关注。随着信息技术的快速发展，网络数据规模迅速增长。然而，大规模网络中的节点中心性计算非常耗时。并行计算是加速节点中心性计算的一种方法。GPU作为现代计算机的核心组件，能够使大量核心任务并行工作，具有大数据处理能力，已被广泛用于加速计算。因此，根据GPU的并行特性，我们设计了并行算法来计算三种广泛使用的节点中心性，即接近中心性、中介中心性和PageRank中心性。首先，根据它们的定义将这三种节点中心性分为两组；其次，通过将不同节点的中心性计算映射到GPU中的不同块或线程来设计并行算法；第三，得益于所设计的并行算法，我们分析了几个网络中不同中心性之间的相关性。实验结果表明，本文设计的并行算法能够加速大规模网络中节点中心性的计算，并且接近中心性和中介中心性虽然都基于最短路径，但它们之间的相关性较弱。
