Affiliations: [a] Department of Computer Science and Engineering, South China University of Technology, Guangzhou, China
| [b] Department of Computer Science, Hong Kong Baptist University, Kowloon Tong, Hong Kong
Correspondence:
[*]
Corresponding author. Lu Lu, Department of Computer Science and Engineering, South China University of
Technology, Guangzhou 510006, China. Tel.: +86 138 0291 8651; E-mail: [email protected].
Abstract: 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 Θ (n3). 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.
