Graphlet Degree Vector方法的优化与并行  

Optimization and parallelization of Graphlet Degree Vector method

作　　者：宋祥帅 杨伏长 谢江[1] 张武[1,2] SONG Xiangshuai;YANG Fuzhang;XIE Jiang;ZHANG Wu(School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China;Shanghai Institute of Applied Mathematics and Mechanics(Shanghai University),Shanghai 200444,China)

机构地区：[1]上海大学计算机工程与科学学院,上海200444 [2]上海大学上海市应用数学与力学研究所,上海200444

出　　处：《计算机应用》2020年第2期398-403,共6页journal of Computer Applications

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

摘　　要：Graphlet Degree Vector(GDV)是一种研究生物网络的重要方法,能揭示生物网络中各节点与其局部网络结构的相关性,但随着需要挖掘的自同构轨道数量的增加以及生物网络规模的增大,GDV方法的时间复杂度会呈指数级增长。针对这个问题,在现有串行GDV方法的基础上,实现了基于消息传递接口(MPI)的GDV方法并行化;此外又将GDV方法进行了改进并将改进后的方法实现了并行优化,改进后的方法在寻找不同节点自同构轨道的过程中优化了计算过程以解决重复计算的问题,同时结合负载均衡策略合理分配任务。模拟网络数据和真实生物网络数据上的实验结果表明,并行化的GDV方法与改进后的并行化GDV方法都具有较好的并行性能,并且对不同类型不同规模的网络都具有较强的适用性,扩展性强,可有效地保持寻找网络中自同构轨道的高效率。Graphlet Degree Vector(GDV)is an important method for studying biological networks,and can reveal the correlation between nodes in biological networks and their local network structures.However,with the increasing number of automorphic orbits that need to be researched and the expanding biological network scale,the time complexity of the GDV method will increase exponentially.To resolve this problem,based on the existing serial GDV method,the parallelization of GDV method based on Message Passing Interface(MPI)was realized.Besides,the GDV method was improved and the parallel optimization of the optimized method was realized.The calculation process was optimized to solve the problem of double counting when searching for automorphic orbits of different nodes by the improved method,at the same time,the tasks were allocated reasonably combining with the load balancing strategy.Experimental results of simulated network data and real biological network data indicate that parallel GDV method and the improved parallel GDV method both obtain better parallel performance,they can be widely applied to different types of networks with different scales,and have good scalability.As a result,they can effectively maintain the high efficiency of searching for automorphic orbits in the network.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]