An optimal parallel implementation of Markov Clustering based on the coordination of CPU and GPU

Markov Clustering algorithm provides an effective method for network clustering problem, especially including community problem and bioinformatics. However, the expansion operation is the most time-consuming procedure, since the multiplication of two large-scale phalanxes can cause the time complexity of Θ (n³). Considering that each element value calculation is independent from others, expansion and inflation can be parallel-executed on the multi-core GPU. First, a basic parallel implementation of Markov Clustering which needs the whole adjacent matrix is proposed as a traditional method to improve the performance. In addition, the adjacent matrix is usually sparse and sometimes ultra-sparse. Hence, an optimal parallel implementation working with the CSR∗CSC multiplication has been developed, which significantly decreases the space needed to store the matrix and promotes the performance of the expansion to the extent. The experimental results show that Sparse-MCL is more effective than CPU-MCL and P-MCL when dealing with the big scale network.