n-度中心度与k-压力中心度及其并行算法

doi:10.12052/gdutxb.190156

广东工业大学学报 ›› 2020, Vol. 37 ›› Issue (03): 36-41.doi: 10.12052/gdutxb.190156

n-度中心度与k-压力中心度及其并行算法

饶东宁¹, 林卓毅¹, 魏来²

1. 广东工业大学计算机学院, 广东广州 510006;
2. 香港大学经济与金融学院, 中国香港 999077

收稿日期:2019-12-17 出版日期:2020-05-12 发布日期:2020-05-12
通信作者: 林卓毅(1992-),男,硕士研究生,主要研究方向为金融智能,E-mail:13570113148@163.com E-mail:13570113148@163.com
作者简介:饶东宁(1977-),男,副教授,博士,主要研究方向为智能规划、金融智能
基金资助:
广东省自然科学基金资助项目（2016A030313700，2016A030313084）

n-Degree and k-Stress Centrality with Parallel Algorithms

Rao Dong-ning¹, Lin Zhuo-yi¹, Wei Lai²

1. School of Computers, Guangdong University of Technology, Guangzhou 510006, China;
2. School of Economics and Finance, The University of Hong Kong, Hong Kong 999077, China

Received:2019-12-17 Online:2020-05-12 Published:2020-05-12

摘要/Abstract

摘要： 网络中心度是网络分析的重要指标。文章提出n-度中心度和k-压力中心度以补充网络中心度的研究，此外，并行算法能提高大规模网络的计算效率。为此，在设计网络中心度并行工具包的同时，设计并实现n-度中心度和k-压力中心度的并行算法。工具包的设计基于Spark框架的Pregel方法，并通过BoardEx社交网络测试性能。实验证明工具包的可行性与可拓展性。

关键词: 网络中心度, 并行算法, 工具包, Spark, Pregel

Abstract: Network centrality is important for network analysis. Therefore, n-Degree and k-Stress centrality are proposed to enrich the analysis options using network centrality. On the other hand, for large scale networks, parallel algorithms are necessary for fast computation. To this end, parallel algorithms for the n-Degree and k-Stress centrality are designed and implemented along with 11 existing centralities in a toolkit. The toolkit is based on Spark Pregel, and tested on the BoardEx social network. Experiments show the feasibility and scalability of the toolkit.

Key words: network centrality, parallel algorithm, toolkit, Spark, Pregel

中图分类号:

TP182

饶东宁, 林卓毅, 魏来. n-度中心度与k-压力中心度及其并行算法[J]. 广东工业大学学报, 2020, 37(03): 36-41.

Rao Dong-ning, Lin Zhuo-yi, Wei Lai. n-Degree and k-Stress Centrality with Parallel Algorithms[J]. Journal of Guangdong University of Technology, 2020, 37(03): 36-41.

参考文献

[1] FREEMAN L C. Centrality in social networks conceptual clarification [J]. Social Networks, 1978, 1(3): 215-239
[2] 吴信东, 董丙冰, 堵新政, 等. 数据治理技术[J]. 软件学报, 2019, 30(9): 2830-2856 WU X D, DONG B B, DU X Z, et al. Data governance technology [J]. Journal of Software, 2019, 30(9): 2830-2856
[3] 陈磊, 吴晓晖. 基于Hadoop的分布式集群大数据动态存储系统设计[J]. 中国电子科学研究院学报, 2019, 14(6): 593-598 CHEN L, WU X H. Design of distributed cluster big data dynamic storage system based on Hadoop [J]. Journal of China Academy of Electronics and Information Technology, 2019, 14(6): 593-598
[4] 廖旺坚, 黄永峰, 包从开. Spark并行计算框架的内存优化[J]. 计算机工程与科学, 2018, 40(4): 587-593 LIAO W J, HUANG Y F, BAO C K. Memory optimization of Spark parallel computing framework [J]. Computer Engineering & Science, 2018, 40(4): 587-593
[5] SINGH R, CHAKRABORTY A, MANOJ B S. GFT centrality: a new node importance measure for complex networks [J]. Physica A: Statistical Mechanics and its Applications, 2017, 487: 185-195
[6] MEDEIROS D S V, CAMPISTA M E M, MITTON N, et al. The power of quasi-shortest paths: ρ-geodesic betweenness centrality [J]. IEEE Transactions on Network Science and Engineering, 2017, 4(3): 187-200
[7] 饶东宁, 温远丽, 魏来, 等. 基于Spark平台的社交网络在不同文化环境中的中心度加权算法[J]. 广东工业大学学报, 2017, 34(3): 15-20 RAO D N, WEN Y L, WEI L, et al. A weighted centrality algorithm for social networks based on Spark platform in different cultural environments [J]. Journal of Guangdong University of Technology, 2017, 34(3): 15-20
[8] 王露, 郭强, 刘建国. 基于加权方法的节点重要性度量[J]. 计算机应用研究, 2018, 35(5): 1426-1428 WANG L, GUO Q, LIU J G. Measuring node importance based on weighted nonlinear method [J]. Application Research of Computers, 2018, 35(5): 1426-1428
[9] 乔少杰, 郭俊, 韩楠, 等. 大规模复杂网络社区并行发现算法[J]. 计算机学报, 2017, 40(3): 687-700 QIAO S J, GUO J, HAN N, et al. Parallel agorithm for discovering communities in large-scale complex networks [J]. Chinese Journal of Computers, 2017, 40(3): 687-700
[10] MA T, YUE M, QU J, et al. PSPLPA: probability and similarity based parallel label propagation algorithm on spark [J]. Physica A: Statistical Mechanics and its Applications, 2018, 503: 366-378
[11] 艾川, 陈彬, 刘亮, 等. 基于Pregel的大规模网络传播仿真算法设计及实现[J]. 中国科学: 信息科学, 2018, 48(7): 932-946 AI C, CHEN B, LIU L, et al. Design and implementation of large-scale network propagation simulation method inspired by Pregel mechanism [J]. Sci Sin Inform, 2018, 48(7): 932-946
[12] Borgatti S P, Everett M G. A graph-theoretic perspective on centrality [J]. Social Networks, 2006, 28(4): 466-484
[13] SHIMBEL A. Structural parameters of communication networks [J]. The Bulletin of Mathematical Biophysics, 1953, 15(4): 501-507
[14] MALEWICZ G, AUSTERN M H, BIK A J C, et al. Pregel: a system for large-scale graph processing[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. Indianapolis: ACM, 2010: 135-146.
[15] ZAHARIA M, CHOWDHURY M, FRANKLIN M J, et al. Spark: cluster computing with working sets [J]. HotCloud, 2010, 10(10): 95
[16] BENZI J, DAMODARAN M. Parallel three dimensional direct simulation Monte Carlo for simulating micro flows [J]. Lect Notes Comput Sci Eng, 2009, 67: 91-98
[17] 饶东宁, 王军星, 魏来, 等. 并行最小割算法及其在金融社交网络中的应用[J]. 广东工业大学学报, 2018, 35(2): 46-50 RAO D N, WANG J X, WEI L, et al. Parallel minimal cut set algorithm and its application in financial social networks [J]. Journal of Guangdong University of Technology, 2018, 35(2): 46-50
[18] 廖志军. 分布式K-Core算法加速求解最大团问题及在金融社交网络中应用[D]. 广州: 暨南大学, 2018.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

n-度中心度与k-压力中心度及其并行算法

n-Degree and k-Stress Centrality with Parallel Algorithms

HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

Metrics

本文评价

推荐阅读 0

[1]	饶东宁, 王军星, 魏来, 王雅丽. 并行最小割算法及其在金融社交网络中的应用[J]. 广东工业大学学报, 2018, 35(02): 46-50.
[2]	林穗, 赵菲. 基于Spark的线性模型在广告投放系统中的应用研究[J]. 广东工业大学学报, 2016, 33(05): 28-33.
[3]	陈培文, 傅秀芬. 采用SVM方法的文本情感极性分类研究[J]. 广东工业大学学报, 2014, 31(3): 95-101.
[4]	张光富，陈松龄，唐平，侯光辉. 牙齿三维虚拟切片交互式定位与二次提取[J]. 广东工业大学学报, 2012, 29(3): 54-58.
[5]	王丹丹, 郭大昌, 王静. 星图应用哈米尔顿拉丁方的并行路由算法[J]. 广东工业大学学报, 2011, 28(1): 62-67.