On Ranking Nodes using kNN Graphs, Shortest-paths and GPUs

Arefin, A.S., Berretta, R. and Moscato, P.

    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 kNN graphs from DNA microarray data sets. The relationship among the genes in the kNN 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 modi cations.
Cite as: Arefin, A.S., Berretta, R. and Moscato, P. (2015). On Ranking Nodes using kNN Graphs, Shortest-paths and GPUs. In Proc. Thirteenth Australasian Data Mining Conference (AusDM 2015) Sydney, Australia. CRPIT, 168. Ong, K.L., Zhao, Y., Stone, M.G. and Islam, M.Z. Eds., ACS. 29-38
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS