.png){kind=icon}
.png){kind=icon}
Return
Efficient parallel algorithm for detecting influential nodes in large biological networks on the Graphics Processing Unit
.png){kind=icon}
PRE
AI
DOI：10.1016/j.future.2019.12.038.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In biological networks, some nodes are more influential than others. The most influential nodes are those whose elimination induces a network collapse, and detecting these nodes is crucial in many circumstances. However, this is a difficult task when the size of the biological networks is large. In this paper, we have designed and implemented an efficient parallel algorithm for detecting influential nodes for large biological networks by exploiting a Graphics Processing Unit (GPU). The essential concept behind the proposed parallel algorithm is that several computationally expensive procedures in detecting influential nodes are redesigned and transformed into quite efficient GPU-accelerated primitives such as parallel sort, scan, and reduction. Four local metrics, including the Degree Centrality (DC), Companion Behavior (CB), Clustering Coefficient (CC), and H-Index, are used to measure the nodal influence. To evaluate the efficiency of the proposed parallel algorithm, five large real biological networks are employed in the experiments. The experimental results show that (1) the proposed parallel algorithm can achieve speedups of approximately 48 similar to 94 over the corresponding serial algorithm; (2) compared to a baseline parallel algorithm developed on a multi-core CPU, the proposed parallel algorithm yields speedups of 5 similar to 9 for DC and H-Index, while it is slightly slower for CB and CC due to the uneven degree distribution; and (3) when using DC and H-Index, the proposed parallel algorithm is capable of detecting the influential nodes in a large biological network consisting of 150 million edges in less than 3 s. (C) 2019 Elsevier B.V. All rights reserved.
Keywords:
Biological networks
Influential nodes
Degree Centrality
Clustering Coefficient
H-Index
Parallel algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
F
IF:
6.1
Papers:
6.8K
Citations:
2.3W