Graphlet Degree Vector方法的优化与并行

doi:10.11772/j.issn.1001-9081.2019081387

《计算机应用》唯一官方网站 ›› 2020, Vol. 40 ›› Issue (2): 398-403.DOI: 10.11772/j.issn.1001-9081.2019081387

• 2019年全国开放式分布与并行计算学术年会(DPCS 2019)论文 • 上一篇下一篇

Graphlet Degree Vector方法的优化与并行

宋祥帅¹, 杨伏长¹, 谢江¹(), 张武¹^,²

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

收稿日期:2019-07-31 修回日期:2018-08-13 接受日期:2019-09-17 发布日期:2019-09-29 出版日期:2020-02-10
通讯作者: 谢江
作者简介:宋祥帅（1995—），男，山东聊城人，硕士研究生，CCF会员，主要研究方向：生物信息学，机器学习
杨伏长（1994—），男，福建宁德人，硕士研究生，CCF会员，主要研究方向：生物信息学
张武（1957—），男，江西武宁人，教授，博士，CCF杰出会员，主要研究方向：高性能计算、生物信息学、计算流体力学。
基金资助:
国家自然科学基金面上项目(61873156)

Optimization and parallelization of Graphlet Degree Vector method

Xiangshuai SONG¹, Fuzhang YANG¹, Jiang XIE¹(), Wu ZHANG¹^,²

^1.School of Computer Engineering and Science，Shanghai University，Shanghai 200444，China
^2.Shanghai Institute of Applied Mathematics and Mechanics （Shanghai University），Shanghai 200444，China

Received:2019-07-31 Revised:2018-08-13 Accepted:2019-09-17 Online:2019-09-29 Published:2020-02-10
Contact: Jiang XIE
About author:SONG Xiangshuai， born in 1995， M. S. candidate. His research interests include bioinformatics， machine learning.
YANG Fuzhang， born in 1994， M. S. candidate. His research interests include bioinformatics.
ZHANG Wu， born in 1957， Ph. D.， professor. His research interests include high performance computing， bioinformatics， computational fluid mechanics.
Supported by:
Surface Program of National Natural Science Foundation of China(61873156)

摘要/Abstract

摘要：

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

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

Abstract:

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.

Key words: Graphlet Degree Vector (GDV) method, biological network, automorphic orbit, subgraph enumeration, parallelization, Message Passing Interface (MPI)

中图分类号:

TP301.6

宋祥帅, 杨伏长, 谢江, 张武. Graphlet Degree Vector方法的优化与并行[J]. 计算机应用, 2020, 40(2): 398-403.

Xiangshuai SONG, Fuzhang YANG, Jiang XIE, Wu ZHANG. Optimization and parallelization of Graphlet Degree Vector method[J]. Journal of Computer Applications, 2020, 40(2): 398-403.

图/表 10

图1 图元及图元向量

Fig. 1 Graphlets and graphlet orbits

图2 无向生物网络实例

Fig. 2 Example of undirected biological network

表1 图2中5个节点在GA网络中图元向量的数量

Tab. 1 Number of graphlet orbits of the five nodes in the GA network of Fig. 2

节点编号	轨道编号
节点编号	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
1	4	0	0	6	0	0	0	0	0	0	0	0	0	0	4
2	4	0	0	6	3	3	0	0	0	0	0	0	0	0	4
3	4	0	0	6	2	6	0	0	0	0	0	0	0	0	4
4	4	0	0	6	2	6	0	0	0	0	0	0	0	0	4
5	4	0	0	6	8	0	0	0	0	0	0	0	0	0	4

图3 GDV方法的主要步骤

Fig. 3 Main steps of GDV method

表2 五个模拟网络数据集

Tab. 2 Five simulated network datasets

网络编号	节点数	网络类型	网络编号	节点数	网络类型
1	500	无标度	4	1 000	小世界
2	800	无标度	5	1 000	随机
3	1 000	无标度

图4 GDV方法的并行性能

Fig. 4 Parallel performance of GDV method

图5 无标度网络在解决重复计算前后的时间消耗

Fig. 5 Time consumption before and after solving double counting in scale-free network

图6 解决重复计算后的并行性能

Fig. 6 Parallel performance after solving double counting

图7 采取负载均衡策略后的实验对比

Fig. 7 Experimental comparison after adopting load balancing strategy

图8 无标度网络的并行性能

Fig. 8 Parallel performance of scale-free networks

参考文献 23

1	GOSAK M， MARKOVIČ R， DOLENŠEK J， et al. Network science of biological systems at different scales： a review［J］. Physics of Life Reviews， 201， 24：118-135. 10.3389/fphys.2021.612233
2	GAUDELET T， MALOD-DOGNIN N， PRŽULJ N. Higher-order molecular organization as a source of biological function［J］. Bioinformatics， 2018， 34（17）：i944-i953. 10.1093/bioinformatics/bty570
3	PRŽULJ N. Biological network comparison using graphlet degree distribution［J］. Bioinformatics， 2007， 23（2）：e177-e183. 10.1093/bioinformatics/btl301
4	MILENKOVIĆ T， PRŽULJ N. Uncovering biological network function via graphlet degree signatures［J］. Cancer Informatics， 2008， 6：257-273. 10.4137/cin.s680
5	XIE J， LU D， LI J， et al. Kernel differential subgraph reveals dynamic changes in biomolecular networks［J］. Journal of Bioinformatics and Computational Biology， 2017， 16（1）： Article No. 1750027. 10.1142/s0219720017500275
6	RADICCHI F， CASTELLANO C， CECCONI F， et al. Defining and identifying communities in networks［J］. Proceedings of the National Academy of Sciences of the United States of America， 2004， 101（9）：2658-2663． 10.1073/pnas.0400054101
7	PRŽULJ N， CORNEIL D G， JRRISICA I. Modeling interactome： scale-free or geometric？［J］. Bioinformaties， 2004， 20（18）： 3508-3515． 10.1093/bioinformatics/bth436
8	PRZULJ N. Biological network comparison using graphlet degree distribution［J］. Cancer Inform， 2008， 6： 257-273. 10.4137/cin.s680
9	KUCHAIEV O， MILENKOVIĆ T， MEMIŠEVIĆ V， et al. Topoiogical network alignment uncovers biological function and phylogeny［J］. Journal of the Royal Society Interface， 2010， 7（50）： 1341-1354. 10.1098/rsif.2010.0063
10	MILENKOVIĆ T， NG W L， HAYES W， et al. Optimal network alignment with graphlet degree vectors［J］. Cancer Informatics， 2010， 9：121-137. 10.4137/cin.s4744
11	RIBEIRO P， SILVA F， LOPES L. Parallel calculation of subgraph census in biological networks［EB/OL］. ［2018-05-20］. . 10.5220/0002749600560065
12	安幸. 基于随机游走的Graphlet采样算法优化［D］. 武汉：华中科技大学， 2018：3-4.
	AN X. Two optimizations for Graphlet random walk sampling algorithm［D］. Wuhan： Huazhong University of Science and Technology， 2018： 3-4.
13	HOČEVAR T， DEMŠAR J. A combinatorial approach to graphlet counting［J］. Bioinformatics， 2014， 30（4）：559-565. 10.1093/bioinformatics/btt717
14	AHMED N K， NEVILLE J， ROSSI R A， et al. Efficient graphlet counting for large networks［C］// Proceedings of the 2015 IEEE International Conference on Data Mining. Piscataway： IEEE， 2015： 1-10. 10.1109/icdm.2015.141
15	肖碧玉，李先彬，沈良忠，等.比较图元向量和点的聚类系数对差异网络的研究［J］.生物信息学，2013，11（4）：264-270. 10.3969/j.issn.1672-5565.2013-04.20130404
	XIAO B Y， LI X B， SHEN L Z， et al. Comparing graphlet orbit and clustering coefficient in differentially network［J］. Chinese Journal of Bioinformatics， 2013， 11（4）： 264-270. 10.3969/j.issn.1672-5565.2013-04.20130404
16	杨伏长，朱嘉富，孙佳敏，等. 生物复杂网络motif发现的并行算法［J］. 计算机应用， 2019，39（1）： 72-77. 10.11772/j.issn.1001-9081.2018071655
	YANG F Z， ZHU J F， SUN J M， et al. Parallel algorithm for bio-complex network motif discovery［J］. Journal of Computer Applications， 2019， 39（1）： 72-77. 10.11772/j.issn.1001-9081.2018071655
17	肖碧玉，李先斌，刘文斌. 基于图元向量的差异共表达分析研究［J］.电子学报， 2015， 43（10）：2009-2013. 10.3969/j.issn.0372-2112.2015.10.019
	XIAO B Y， LI X B， LIU W B. Mining differential co-expression clusters based on graphlet orbits［J］. Acta Electronica Sinica， 2015， 43（10）： 2009-2013. 10.3969/j.issn.0372-2112.2015.10.019
18	HAGBERG A H， SWART P J， SCHULT D A. Exploring network structure， dynamics， and function using NetworkX［R］. Los Alamos： Los Alamos National Laboratory， 2008.
19	BARABÁSI A L， ALBERT R. Emergence of scaling in random networks［J］. Science， 1999， 286（5439）：509-512. 10.1126/science.286.5439.509
20	WATTS D J， STROGATZ S H. Collective dynamics of ‘small-world’ networks［J］. Nature， 1998， 393（6684）：440-442. 10.1038/30918
21	KIM J H， VU V H. Generating random regular graphs［C］// Proceedings of the 35th Annual ACM Symposium on Theory of Computing. New York： ACM， 2003：213-222. 10.1145/780542.780576
22	STRING. Homepage of STRING［EB/OL］. ［2018-05-20］. . 10.1177/0003131318759908
23	BARABÁSI A L， OLTVAI Z N. Network biology： understanding the cell’s functional organization［J］. Nature Reviews Genetics， 2004， 5（2）： 101-113. 10.1038/nrg1272

[1]	王周恺, 张炯, 马维纲, 王怀军. 面向高速列车监测数据的并行解压缩算法[J]. 计算机应用, 2021, 41(9): 2586-2593.
[2]	蒋林, 施佳琪, 李远成. 可重构结构下合成视点失真变化算法并行设计与实现[J]. 计算机应用, 2021, 41(6): 1734-1740.
[3]	郭良敏, 朱莹, 孙丽萍. 障碍空间中基于并行蚁群算法的k近邻查询[J]. 计算机应用, 2019, 39(3): 790-795.
[4]	李龙洋, 董一鸿, 施炜杰, 潘剑飞. SQM:基于Spark的大规模单图上的子图匹配算法[J]. 计算机应用, 2019, 39(1): 46-50.
[5]	孙佳敏, 朱嘉富, 杨伏长, 谢江. 大规模生物网络马尔可夫聚类的并行化算法[J]. 计算机应用, 2019, 39(1): 66-71.
[6]	杨伏长, 朱嘉富, 孙佳敏, 谢江. 生物复杂网络motif发现的并行算法[J]. 计算机应用, 2019, 39(1): 72-77.
[7]	肖成龙, 林军, 王珊珊, 王宁. 面向高层次综合的自定义指令自动识别方法[J]. 计算机应用, 2018, 38(7): 2024-2031.
[8]	崔晨, 郑林江, 韩凤萍, 何牧君. 基于内存的HBase二级索引设计[J]. 计算机应用, 2018, 38(6): 1584-1590.
[9]	王鹏, 周岩. 面向高性能应用的MPI大数据处理[J]. 计算机应用, 2018, 38(12): 3496-3499.
[10]	张承畅, 张华誉, 罗建昌, 何丰. 基于云计算和改进K-means算法的海量用电数据分析方法[J]. 计算机应用, 2018, 38(1): 159-164.
[11]	刘有耀, 杨鹏程. 基于JavaCC的C代码自动并行化的设计与实现[J]. 计算机应用, 2016, 36(9): 2422-2426.
[12]	韩逢庆, 宋志坚, 余锐. 海量图片快速去重技术[J]. 计算机应用, 2016, 36(7): 1797-1800.
[13]	曾雪琳, 吴斌. 基于位置的社会化网络的并行化推荐算法[J]. 计算机应用, 2016, 36(2): 316-323.
[14]	林炀, 江育娥, 林劼. 基于分布式架构的时间序列局部相似检测算法[J]. 计算机应用, 2016, 36(12): 3285-3291.
[15]	于苹苹, 倪建成, 姚彬修, 李淋淋, 曹博. 基于Spark框架的高效KNN中文文本分类算法[J]. 计算机应用, 2016, 36(12): 3292-3297.

Graphlet Degree Vector方法的优化与并行

Optimization and parallelization of Graphlet Degree Vector method

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 23

相关文章 15

编辑推荐

Metrics