Parallel algorithm of betweenness centrality for dynamic networks

doi:10.11772/j.issn.1001-9081.2022071121

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (7): 1987-1993.DOI: 10.11772/j.issn.1001-9081.2022071121

Special Issue: 第39届CCF中国数据库学术会议(NDBC 2022)

• The 39th CCF National Database Conference (NDBC 2022) • Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP311

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

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

Figures/Tables 8

References 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

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 21

Related Articles 15

Recommended Articles

Metrics

[1]	Shiliang LIU, Yi WANG, Yinglong MA. Non-overlapping community detection with imbalanced community sizes [J]. Journal of Computer Applications, 2024, 44(11): 3396-3402.
[2]	Ming DU, Wanli GU, Junfeng ZHOU, Zhijun WANG. Community search method based on motif connectivity [J]. Journal of Computer Applications, 2023, 43(7): 2190-2199.
[3]	Xiangyu LUO, Ke YAN, Yan LU, Tian WANG, Gang XIN. Nonuniform time slicing method based on prediction of community variance [J]. Journal of Computer Applications, 2023, 43(11): 3457-3463.
[4]	LI Zhanli, LI Ying, LUO Xiangyu, LUO Yingxiao. Local community detection algorithm based on Monte-Carlo iterative solving strategy [J]. Journal of Computer Applications, 2023, 43(1): 104-110.
[5]	Huanliang SUN, Cheng PENG, Junling LIU, Jingke XU. Community structure representation learning for "15-minute living circle" [J]. Journal of Computer Applications, 2022, 42(6): 1782-1788.
[6]	Yuan GUO, Xuewen WANG, Chong WANG, Jinlin JIANG. Nonlinear scrambling diffusion synchronization image encryption based on dynamic network [J]. Journal of Computer Applications, 2022, 42(1): 162-170.
[7]	LI Yafang, LIANG Ye, FENG Weiwei, ZU Baokai, KANG Yujian. Deep network embedding method based on community optimization [J]. Journal of Computer Applications, 2021, 41(7): 1956-1963.
[8]	ZHANG Yuanjun, ZHANG Xihuang. Dynamic network representation learning model based on graph convolutional network and long short-term memory network [J]. Journal of Computer Applications, 2021, 41(7): 1857-1864.
[9]	Huibo LI, Yunxiao ZHAO, Liang BAI. Dynamic graph representation learning method based on deep neural network and gated recurrent unit [J]. Journal of Computer Applications, 2021, 41(12): 3432-3437.
[10]	LUO Xiangyu, LI Jianan, LUO Xiaoxia, WANG Jia. Improved community evolution relationship analysis method for dynamic graphs [J]. Journal of Computer Applications, 2020, 40(8): 2313-2318.
[11]	SHAO Hao, WANG Lunwen, DENG Jian. Important node identification method for dynamic networks based on H operation [J]. Journal of Computer Applications, 2019, 39(9): 2669-2674.
[12]	FU Chaojiang, WANG Tianqi, LIN Yuerong. Parallel algorithm for explicit finite element analysis based on efficient parallel computational strategy [J]. Journal of Computer Applications, 2018, 38(4): 1072-1077.
[13]	CHEN Yuzhong, GUO Songrong, CHEN Hong, LI Wanhua, GUO Kun, HUANG Qicheng. Electricity customers arrears alert based on parallel classification algorithm [J]. Journal of Computer Applications, 2016, 36(6): 1757-1761.
[14]	CHU Zheng, YU Jiong, LU Liang, YING Changtian, BIAN Chen, WANG Yuefei. Parallel access strategy for big data objects based on RAMCloud [J]. Journal of Computer Applications, 2016, 36(6): 1526-1532.
[15]	WANG Chunbo, DONG Hongbin, YIN Guisheng, LIU Wenjie. Super pixel segmentation algorithm based on Hadoop [J]. Journal of Computer Applications, 2016, 36(11): 2985-2992.