计算机应用

作者：孙佳敏, 朱嘉富, 杨伏长, 谢江

单位：上海大学 计算机工程与科学学院, 上海 200444

关键词：消息传递接口,并行化,马尔可夫聚类,Cannon算法,大规模生物网络

基金：国家重点研发计划重点专项（2016YFC1401900）；上海市自然科学基金资助项目（17ZR1409900）。

马尔可夫聚类算法（MCL）是在大规模生物网络中寻找模块的一个有效方法，能够挖掘网络结构和功能影响力较大的模块。算法涉及到大规模矩阵计算，因此复杂度可达立方阶次。针对复杂度高的问题，提出了基于消息传递接口（MPI）的并行化马尔可夫聚类算法以提高算法的计算性能。首先，生物网络转化成邻接矩阵；然后，根据算法的特性，按照矩阵的规模判断并重新生成新矩阵以处理非平方倍数矩阵的计算；其次，并行计算通过按块分配的方式能够有效地实现任意规模矩阵的运算；最后，循环并行计算直至收敛，得到网络聚类结果。通过模拟网络和真实生物网络数据集的实验结果表明，与全块集体式通信（FCC）并行方法相比，平均并行效率提升了10个百分点以上，因此可以将该优化算法应用在不同类型的大规模生物网络中。

来源：2019年第1期

《计算机应用》期刊编辑部

查看计算机应用杂志2019年第1期