论文部分内容阅读
Markov Clustering algorithm [1,13] provides an effective method for network clustering problem,especially including community problem and bioinformatics like protein-protein interaction.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 each other,expansion and inflation can be parallel-executed on the multi-core GPU.First,a basic parallel implementation of Markov Clustering(P-MCL)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 [2] multiplication(Sparse-MCL)has been developed,which significantly decreases the space needed to store the matrix and promotes the performance of the expansion greatly.In our experimental results,P-MCL realized a high speedup ranged from about 40x to 150x as the scale of the network data increased,while Sparse-MCL attained a more fantastic speedup ranged from about 60x to 200x.Even Sparse-MCL played a great effect when MCL implemented with CPU and P-MCL became powerless in dealing with the network which contains over than 7000 nodes.