计算机应用

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

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

关键词：网络motif发现,子图枚举,同构比较,并行化,消息传递接口

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

生物复杂网络motif发现是一种研究生物网络的重要方法，它基于复杂网络的理论研究，以新的视角来研究生命现象和生命机制，但是在处理较大的网络规模或者需挖掘较大的motif时计算效率低。针对这个问题，在现有串行网络motif发现算法ESU的基础上，提出一种基于消息传递接口（MPI）的并行化ESU算法。该方法在ESU计算过程中优化了节点值以解决节点值依赖问题，并以ESU算法的子图发现策略统计各节点子图数，利用动态规划策略寻找最佳节点分配策略以解决负载不均衡问题。模拟网络数据和真实生物网络数据的实验结果表明，并行化ESU算法优化了节点值依赖问题，实现了基于动态规划的负载均衡策略，其运行时间比串行算法缩短了90%，并且该并行算法对不同类型不同规模的网络都具有较强的适用性，有效地提高了网络motif发现问题的计算效率。

来源：2019年第1期

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

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