计算机应用

作者：宋祥帅, 杨伏长, 谢江, 张武

单位：1.上海大学 计算机工程与科学学院，上海 200444；2.上海大学 上海市应用数学与力学研究所，上海 200444

关键词：Graphlet Degree Vector方法,生物网络,自同构轨道,子图枚举,并行化,消息传递接口

基金：国家自然科学基金面上项目(61873156)

Graphlet Degree Vector （GDV）是一种研究生物网络的重要方法，能揭示生物网络中各节点与其局部网络结构的相关性，但随着需要挖掘的自同构轨道数量的增加以及生物网络规模的增大，GDV方法的时间复杂度会呈指数级增长。针对这个问题，在现有串行GDV方法的基础上，实现了基于消息传递接口（MPI）的GDV方法并行化；此外又将GDV方法进行了改进并将改进后的方法实现了并行优化，改进后的方法在寻找不同节点自同构轨道的过程中优化了计算过程以解决重复计算的问题，同时结合负载均衡策略合理分配任务。模拟网络数据和真实生物网络数据上的实验结果表明，并行化的GDV方法与改进后的并行化GDV方法都具有较好的并行性能，并且对不同类型不同规模的网络都具有较强的适用性，扩展性强，可有效地保持寻找网络中自同构轨道的高效率。

来源：2020年第2期

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

查看计算机应用杂志2020年第2期