面向动态网络的介数中心度并行算法

doi:10.11772/j.issn.1001-9081.2022071121

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (7): 1987-1993.DOI: 10.11772/j.issn.1001-9081.2022071121

• 第39届CCF中国数据库学术会议(NDBC 2022) • 下一篇

面向动态网络的介数中心度并行算法

刘震宇, 王朝坤(), 郭高扬

清华大学软件学院，北京 100084

收稿日期:2022-07-12 修回日期:2022-08-01 接受日期:2022-08-11 发布日期:2023-07-20 出版日期:2023-07-10
通讯作者: 王朝坤
作者简介:刘震宇（1999—），男，河南南阳人，硕士研究生，CCF会员，主要研究方向：社交网络、社区发现；
王朝坤（1976—），男，江苏东台人，副教授，博士，CCF高级会员，主要研究方向：社交网络分析、图数据管理、大数据系统；
郭高扬（1994—），男，山西运城人，博士研究生，主要研究方向：社交网络、图神经网络、知识图谱构建。
基金资助:
国家自然科学基金资助项目(61872207)

Parallel algorithm of betweenness centrality for dynamic networks

Zhenyu LIU, Chaokun WANG(), Gaoyang GUO

School of Software，Tsinghua University，Beijing 100084，China

Received:2022-07-12 Revised:2022-08-01 Accepted:2022-08-11 Online:2023-07-20 Published:2023-07-10
Contact: Chaokun WANG
About author:LIU Zhenyu， born in 1999， M. S. candidate. His research interests include social network， community detection.
WANG Chaokun， born in 1976， Ph. D.， associate professor. His research interests include social network analysis， graph data management， big data system.
GUO Gaoyang， born in 1994， Ph. D. candidate. His research interests include social network， graph neural network， knowledge graph construction.
Supported by:
National Natural Science Foundation of China(61872207)

摘要/Abstract

摘要：

介数中心度是评价图中节点重要性的一项常用指标，然而在大规模动态图中介数中心度的更新效率很难满足应用需求。随着多核技术的发展，算法并行化已成为解决该问题的有效手段之一。因此，提出一种面向动态网络的介数中心度并行算法（PAB）。首先，通过社区过滤、等距剪枝和分类筛选等操作减少了冗余点对的时间开销；然后，基于对算法确定性的分析和处理实现了并行化。在真实数据集和合成数据集上进行了对比实验，结果显示在添加边更新时PAB的更新效率为并行算法中最新的batch-iCENTRAL的4倍。可见，所提算法能够有效提高动态网络中介数中心度的更新效率。

关键词: 介数中心度, 动态网络, 最短距离, 并行算法, 社区结构

Abstract:

Betweenness centrality is a common metric for evaluating the importance of nodes in a graph. However， the update efficiency of betweenness centrality in large-scale dynamic graphs is not high enough to meet the application requirements. With the development of multi-core technology， algorithm parallelization has become one of the effective ways to solve this problem. Therefore， a Parallel Algorithm of Betweenness centrality for dynamic networks （PAB） was proposed. Firstly， the time cost of redundant point pairs was reduced through operations such as community filtering， equidistant pruning and classification screening. Then， the determinacy of the algorithm was analyzed and processed to realize parallelization. Comparison experiments were conducted on real datasets and synthetic datasets， and the results show that the update efficiency of PAB is 4 times that of the latest batch-iCENTRAL algorithm on average when adding edges. It can be seen that the proposed algorithm can improve the update efficiency of betweenness centrality in dynamic networks effectively.

Key words: betweenness centrality, dynamic network, shortest distance, parallel algorithm, community structure

中图分类号:

TP311

刘震宇, 王朝坤, 郭高扬. 面向动态网络的介数中心度并行算法[J]. 计算机应用, 2023, 43(7): 1987-1993.

Zhenyu LIU, Chaokun WANG, Gaoyang GUO. Parallel algorithm of betweenness centrality for dynamic networks[J]. Journal of Computer Applications, 2023, 43(7): 1987-1993.

图/表 8

参考文献 21

1	FREEMAN L C. A set of measures of centrality based on betweenness ［J］. Sociometry， 1977， 40（1）： 35-41. 10.2307/3033543
2	BADER D A， KINTALI S， MADDURI K， et al. Approximating betweenness centrality ［C］// Proceedings of the 2007 International Workshop on Algorithms and Models for the Web-Graph， LNC 4863. Berlin： Springer， 2007： 124-137.
3	ÖZGÜR A， VU T， ERKAN G， et al. Identifying gene-disease associations using centrality on a literature mined gene-interaction network［J］. Bioinformatics， 2008， 24（13）： i277-i285. 10.1093/bioinformatics/btn182
4	DALY E M， HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANETs ［C］// Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York： ACM， 2007： 32-40. 10.1145/1288107.1288113
5	McLAUGHLIN A， BADER D A. Revisiting edge and node parallelism for dynamic GPU graph analytics ［C］// Proceedings of the 2014 IEEE International Parallel and Distributed Processing Symposium Workshops. Piscataway： IEEE， 2014： 1396-1406. 10.1109/ipdpsw.2014.157
6	JAMOUR F， SKIADOPOULOS S， KALNIS P. Parallel algorithm for incremental betweenness centrality on large graphs［J］. IEEE Transactions on Parallel and Distributed Systems， 2018， 29（3）： 659-672. 10.1109/tpds.2017.2763951
7	SHUKLA K， REGUNTA S C， TONDOMKER S H， et al. Efficient parallel algorithms for betweenness- and closeness-centrality in dynamic graphs ［C］// Proceedings of the 34th ACM International Conference on Supercomputing. New York： ACM， 2020： No.10. 10.1145/3392717.3392743
8	CLEMENTE G P， CORNARO A. Community detection in attributed networks for global transfer market［J］. Annals of Operations Research， 2022： 1-27. 10.1007/s10479-021-04439-9
9	DILMAGHANI S， BRUST M R， RIBEIRO C H C， et al. From communities to protein complexes： a local community detection algorithm on PPI networks［J］. PLoS ONE， 2022， 17（1）： No.e0260484. 10.1371/journal.pone.0260484
10	钱珺，王朝坤，郭高扬.基于社区的动态网络节点介数中心度更新算法［J］.软件学报， 2018， 29（3）： 853-868. 10.13328/j.cnki.jos.005457
	QIAN J， WANG C K， GUO G Y. Community based node betweenness centrality updating algorithms in dynamic networks［J］. Journal of Software， 2018， 29（3）： 853-868. 10.13328/j.cnki.jos.005457
11	BRANDES U. A faster algorithm for betweenness centrality［J］. The Journal of Mathematical Sociology， 2001， 25（2）： 163-177. 10.1080/0022250x.2001.9990249
12	LEE M J， LEE J， PARK J Y， et al. QUBE： a quick algorithm for updating betweenness centrality ［C］// Proceedings of the 21st International Conference on World Wide Web. New York： ACM， 2012： 351-360. 10.1145/2187836.2187884
13	GREEN O， McCOLL R， BADER D A. A fast algorithm for streaming betweenness centrality ［C］// Proceedings of the 2012 ASE/IEEE International Conference on Privacy， Security， Risk and Trust and 2012 ASE/IEEE International Conference on Social Computing. Piscataway： IEEE， 2012： 11-20. 10.1109/socialcom-passat.2012.37
14	MAURYA S K， LIU X， MURATA T. Fast approximations of betweenness centrality with graph neural networks ［C］// Proceedings of the 28th ACM International Conference on Information and Knowledge Management. New York： ACM， 2019： 2149-2152. 10.1145/3357384.3358080
15	CHEHREGHANI M H， BIFET A， ABDESSALEM T. Exact and approximate algorithms for computing betweenness centrality in directed graphs［J］. Fundamenta Informaticae， 2021， 182（3）： 219-242. 10.3233/fi-2021-2071
16	CORMEN T H， LEISERSON C E， RIVEST R L， et al. Introduction to Algorithms［M］. 3rd ed. Cambridge： MIT Press， 2009： 787-788.
17	王堃.基于多核的并行程序设计及优化［D］.南京：南京大学， 2012： 10-16.
	WANG K. Parallel programming and optimization based on multi-core processors［D］. Nanjing： Nanjing University， 2012：10-16.
18	NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks［J］. Physical Review E： Statistical， Nonlinear， and Soft Matter Physics， 2004， 69（2）： No.026113. 10.1103/physreve.69.026113
19	CHEN J， SAAD Y. Dense subgraph extraction with application to community detection［J］. IEEE Transactions on Knowledge and Data Engineering， 2012， 24（7）： 1216-1230. 10.1109/tkde.2010.271
20	RAGHAVAN U N， ALBERT R， KUMARA S. Near linear time algorithm to detect community structures in large-scale networks［J］. Physical Review E： Statistical， Nonlinear， and Soft Matter Physics， 2007， 76（3）： No.036106. 10.1103/physreve.76.036106
21	LEUNG I X Y， HUI P， LIÒ P， et al. Towards real-time community detection in large networks［J］. Physical Review E： Statistical， Nonlinear， and Soft Matter Physics， 2009， 79（6）： No.066107. 10.1103/physreve.79.066107

数据集	节点数	边数	类型
opera_1000	1 000	15 484	无向
opera_10000	10 000	307 562	无向
opera_100000	100 000	1 335 005	无向
ego-Facebook	4 039	88 234	无向
Oregon-010331	10 670	22 002	无向
Oregon-010428	10 886	22 493	无向
p2p-Gnutella25	22 687	54 705	有向
Wiki-Vote	7 115	103 689	有向
Email-Enron	36 692	183 831	无向
Brightkite	58 228	214 078	无向

数据集	节点数	边数	类型
opera_1000	1 000	15 484	无向
opera_10000	10 000	307 562	无向
opera_100000	100 000	1 335 005	无向
ego-Facebook	4 039	88 234	无向
Oregon-010331	10 670	22 002	无向
Oregon-010428	10 886	22 493	无向
p2p-Gnutella25	22 687	54 705	有向
Wiki-Vote	7 115	103 689	有向
Email-Enron	36 692	183 831	无向
Brightkite	58 228	214 078	无向

数据集	时间T/s					加速比Ra
数据集	Br-p	b-iC（+）	b-iC（-）	PAB（+）	PAB（-）	Br-p（+）	Br-p（-）	b-iC（+）	b-iC（-）
opera_1000	1.16	0.21	0.23	0.04	0.06	29.00	19.33	5.25	3.83
opera_10000	264.61	13.95	17.16	0.82	1.58	322.70	167.47	17.01	10.86
opera_100000	15 147.30	1 399.09	1 970.63	160.63	631.26	94.30	24.00	8.71	3.12
ego-Facebook	24.95	2.79	0.87	3.68	0.11	6.78	226.82	0.76	7.91
Oregon-010331	34.40	3.89	4.21	3.50	6.14	9.83	5.60	1.11	0.69
Oregon-010428	36.72	4.14	4.26	3.20	5.86	11.48	6.27	1.29	0.73
p2p-Gnutella25	179.39	16.52	17.89	12.23	35.05	14.67	5.12	1.35	0.51
Wiki-Vote	60.81	4.17	4.50	0.79	1.71	76.97	35.56	5.28	2.63
Email-Enron	773.63	78.82	77.30	55.62	106.68	13.90	7.25	1.42	0.72
Brightkite	2 180.86	193.34	199.84	171.03	434.78	12.75	5.02	1.13	0.46

数据集	时间T/s					加速比Ra
数据集	Br-p	b-iC（+）	b-iC（-）	PAB（+）	PAB（-）	Br-p（+）	Br-p（-）	b-iC（+）	b-iC（-）
opera_1000	1.16	0.21	0.23	0.04	0.06	29.00	19.33	5.25	3.83
opera_10000	264.61	13.95	17.16	0.82	1.58	322.70	167.47	17.01	10.86
opera_100000	15 147.30	1 399.09	1 970.63	160.63	631.26	94.30	24.00	8.71	3.12
ego-Facebook	24.95	2.79	0.87	3.68	0.11	6.78	226.82	0.76	7.91
Oregon-010331	34.40	3.89	4.21	3.50	6.14	9.83	5.60	1.11	0.69
Oregon-010428	36.72	4.14	4.26	3.20	5.86	11.48	6.27	1.29	0.73
p2p-Gnutella25	179.39	16.52	17.89	12.23	35.05	14.67	5.12	1.35	0.51
Wiki-Vote	60.81	4.17	4.50	0.79	1.71	76.97	35.56	5.28	2.63
Email-Enron	773.63	78.82	77.30	55.62	106.68	13.90	7.25	1.42	0.72
Brightkite	2 180.86	193.34	199.84	171.03	434.78	12.75	5.02	1.13	0.46

社区发现算法	模块度	时间T/s
社区发现算法	模块度	PAB（+）	PAB（-）
DSGE	0.17	1.95	2.27
LPA	0.36	1.39	2.02
HANP	0.40	0.82	1.58

面向动态网络的介数中心度并行算法

Parallel algorithm of betweenness centrality for dynamic networks

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 21

相关文章 15

编辑推荐

Metrics

[1]	杜明, 顾万里, 周军锋, 王志军. 基于motif连通性的社区搜索方法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2190-2199.
[2]	李占利, 李颖, 罗香玉, 罗颖骁. 基于Monte-Carlo迭代求解策略的局部社区发现算法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 104-110.
[3]	孙焕良, 彭程, 刘俊岭, 许景科. 面向“15分钟生活圈”社区结构的表示学习[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1782-1788.
[4]	郭媛, 王学文, 王充, 姜津霖. 基于动态网络的非线性置乱扩散同步图像加密[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 162-170.
[5]	张元钧, 张曦煌. 基于图卷积与长短期记忆网络的动态网络表示学习模型[J]. 计算机应用, 2021, 41(7): 1857-1864.
[6]	李亚芳, 梁烨, 冯韦玮, 祖宝开, 康玉健. 基于社区优化的深度网络嵌入方法[J]. 计算机应用, 2021, 41(7): 1956-1963.
[7]	李慧博, 赵云霄, 白亮. 基于深度神经网络和门控循环单元的动态图表示学习方法[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3432-3437.
[8]	罗香玉, 李嘉楠, 罗晓霞, 王佳. 改进的动态图社区演化关系分析方法[J]. 计算机应用, 2020, 40(8): 2313-2318.
[9]	邵豪, 王伦文, 邓健. 基于H运算的动态网络重要节点识别方法[J]. 计算机应用, 2019, 39(9): 2669-2674.
[10]	付朝江, 王天奇, 林悦荣. 基于有效并行求解策略的显式有限元分析并行算法[J]. 计算机应用, 2018, 38(4): 1072-1077.
[11]	褚征, 于炯, 鲁亮, 英昌甜, 卞琛, 王跃飞. 基于内存云的大块数据对象并行存取策略[J]. 计算机应用, 2016, 36(6): 1526-1532.
[12]	陈羽中, 郭松荣, 陈宏, 李婉华, 郭昆, 黄启成. 基于并行分类算法的电力客户欠费预警[J]. 计算机应用, 2016, 36(6): 1757-1761.
[13]	王春波, 董红斌, 印桂生, 刘文杰. 基于Hadoop的超像素分割算法[J]. 计算机应用, 2016, 36(11): 2985-2992.
[14]	何莉, 刘晓东, 李松阳, 张倩. 多核环境下并行粒子群算法[J]. 计算机应用, 2015, 35(9): 2482-2485.
[15]	罗毅平, 邓飞, 周笔锋. 时变时滞复杂动态网络的非脆弱性同步保性能控制[J]. 计算机应用, 2015, 35(2): 364-368.