On ranking nodes using kNN graphs, shortest-paths and GPUs

In this paper, we present graphics processing unit (GPU) based implementations of three popular shortest-path centrality metrics- closeness, eccentricity and betweenness. The basic method is designed to compute the centrality on gene-expression networks, where the network is pre-constructed in the form of <i>k</i>NN graphs from DNA microarray data sets. The relationship among the genes in the <i>k</i>NN graph is determined by the similarity of their expression levels. The proposed method has been applied to a well known breast cancer microarray study and we highlighted the correlation of the highly ranked genes to the time to relapse of the disease. The method is readily applicable to other datasets, where the data points can be recognised in a multidimensional space. It can be applied to other networks (e.g., social networks, the Internet, etc.) with minimal modications