生物复杂网络motif发现的并行算法

论文摘要

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

论文目录

• 0 引言
• 1 网络motif发现
• 2 ESU算法及其并行化实现
•   2.1 串行ESU算法
•     2.1.1 算法实现原理
•     2.1.2 算法分析
•   2.2 ESU算法并行化
•     2.2.1 解决节点值依赖问题
•     2.2.2 网络节点分配过程
•     2.2.3 ESU算法并行框架
• 3 实验与分析
•   3.1 实验环境
•   3.2 实验数据
•   3.3 实验结果与分析
•     3.3.1 优化节点值依赖的结果
•     3.3.2 动态规划策略的结果
•     3.3.3 不同平均节点度的模拟网络的实验结果
•     3.3.4 生物网络的实验结果
• 4 结语

文章来源

类型: 期刊论文

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

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

来源: 计算机应用 2019年01期

年度: 2019

分类: 信息科技,基础科学

专业: 数学,计算机软件及计算机应用

单位: 上海大学计算机工程与科学学院

基金: 国家重点研发计划重点专项(2017YFB0701501),上海市自然科学基金资助项目(17ZR1409900)~~

分类号: TP301.6;O157.5

页码: 72-77

总页数: 6

文件大小: 1328K

下载量: 123