الگوریتم موازی موثر در تشخیص گره های تاثیر گذار
Abstract
۱٫ Introduction
۲٫ Background: Metrics for detecting influential nodes in large biological networks
۳٫ Proposed parallel algorithm for detecting influential nodes in large biological networks
۴٫ Results
۵٫ Discussion
۶٫ Conclusion
Acknowledgments
References
Abstract
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 GPUaccelerated 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∼۹۴ 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∼۹ 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.
Introduction
In recent years, complex network analysis has received increasing attention. Many real complex systems can be abstractly regarded as complex networks for presenting the complexities of real systems [1], such as social networks, technological networks, information networks, and biological networks. Various methods have been proposed for mining information from complex networks. In particular, detecting the influential nodes in complex networks is a topic of interest drawing much attention in this research field [2–۴].
Detecting influential nodes in complex networks can be exploited to mine the features and functions of these networks [2]. Much research has been conducted to rank and identify influential nodes in the aforementioned four network categories. In the detection of influential nodes in various networks, the first critical issue is to select or define the metrics for measuring the influence of each node; the second is to employ or develop specific algorithms to effectively and efficiently determine and rank the influential nodes.
Many metrics have been proposed for detecting the influential nodes in complex networks. These metrics can be roughly divided into two categories [4]: (1) local metrics that are calculated based on the local structures of networks and (2) global metrics that are calculated based on the global structures of networks. For the first category, the most commonly used metrics include the degree centrality, clustering coefficient, and H-Index [5]. For the second category, the most commonly used metrics are the betweenness centrality [6], closeness centrality, PageRank, k-core [7] computed using the k-shell decomposition [8], and the bidirectional k-core (B-core) [9].