| 大规模图中低复杂度分布式算法浅析 |
| |
| 引用本文： | 华强胜,艾明,钱立祥,于东晓,石宣化,金海.大规模图中低复杂度分布式算法浅析[J].南京气象学院学报,2017,9(5):533-543. |
| |
| 作者姓名： | 华强胜 艾明 钱立祥 于东晓 石宣化 金海 |
| |
| 作者单位： | 华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074,华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074,华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074,华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074,华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074,华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074 |
| |
| 基金项目： | 国家自然科学基金（61572216）；中央高校基本科研业务费专项资金（0118210126） |
| |
| 摘 要： | 近年来大规模图分析问题在网络大数据领域发挥着重要作用.经典的图分析问题包括求图的直径、半径、围长、聚类系数、紧密中心度和介数中心度等.集中式算法求解这些图计算问题一般都需要问题规模的平方甚至立方以上复杂度，显然不适用于大规模图.本文旨在从分布式算法角度介绍对这些基本图计算问题具有最坏性能保证的低复杂度（线性时间）算法.此外，本文还将介绍如何通过通信复杂性理论证明分布式图计算问题的下界.
|
| 关 键 词： | 图分析 分布式算法 分布式复杂性 通信复杂性 拥塞模型 |
| 收稿时间： | 2017/7/1 0:00:00 |
Low-complexity distributed algorithms on large-scale graphs:A brief review |
| |
| HUA Qiangsheng,AI Ming,QIAN Lixiang,YU Dongxiao,SHI Xuanhua and JIN Hai.Low-complexity distributed algorithms on large-scale graphs:A brief review[J].Journal of Nanjing Institute of Meteorology,2017,9(5):533-543. |
| |
| Authors: | HUA Qiangsheng AI Ming QIAN Lixiang YU Dongxiao SHI Xuanhua and JIN Hai |
| |
| Institution: | School of Computer Science & Technology, Huazhong University of Science & Technology, Wuhan 430074;Services Computing Technology and System Lab, Huazhong University of Science & Technology, Wuhan 430074,School of Computer Science & Technology, Huazhong University of Science & Technology, Wuhan 430074;Services Computing Technology and System Lab, Huazhong University of Science & Technology, Wuhan 430074,School of Computer Science & Technology, Huazhong University of Science & Technology, Wuhan 430074;Services Computing Technology and System Lab, Huazhong University of Science & Technology, Wuhan 430074,School of Computer Science & Technology, Huazhong University of Science & Technology, Wuhan 430074;Services Computing Technology and System Lab, Huazhong University of Science & Technology, Wuhan 430074,School of Computer Science & Technology, Huazhong University of Science & Technology, Wuhan 430074;Services Computing Technology and System Lab, Huazhong University of Science & Technology, Wuhan 430074 and School of Computer Science & Technology, Huazhong University of Science & Technology, Wuhan 430074;Services Computing Technology and System Lab, Huazhong University of Science & Technology, Wuhan 430074 |
| |
| Abstract: | In recent years,large-scale graph analysis has played an important role in big data computing.The classical graph analysis problems include computing the graph diameter,the radius,the girth,the clustering coefficient and various centrality indices.To solve these problems,centralized algorithms generally require square or even cubic time complexity,which is obviously not applicable to large-scale graphs.In this paper,we aim to briefly review some low complexity (linear time) algorithms for these basic graph problems from a perspective of distributed algorithms.In addition,this paper also shows how to prove the lower bound of distributed graph computing by utilizing the communication complexity theory. |
| |
| Keywords: | graph analysis distributed algorithm distributed complexity communication complexity CONGEST model |
|
| 点击此处可从《南京气象学院学报》浏览原始摘要信息 |
| 点击此处可从《南京气象学院学报》下载免费的PDF全文 |
|
