按:   检索词:   从
   最新录用    过刊检索
大规模图中低复杂度分布式算法浅析
投稿时间:2017-07-01    点此下载全文
引用本文:华强胜,艾明,钱立祥,于东晓,石宣化,金海.大规模图中低复杂度分布式算法浅析[J].南京信息工程大学学报,2017,(5):533~543
摘要点击次数: 62
全文下载次数: 61
作者单位
华强胜 华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074 
艾明 华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074 
钱立祥 华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074 
于东晓 华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074 
石宣化 华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074 
金海 华中科技大学 计算机科学与技术学院, 武汉, 430074;华中科技大学 服务计算技术与系统教育部重点实验室, 武汉, 430074 
基金项目:国家自然科学基金(61572216);中央高校基本科研业务费专项资金(0118210126)
中文摘要:近年来大规模图分析问题在网络大数据领域发挥着重要作用.经典的图分析问题包括求图的直径、半径、围长、聚类系数、紧密中心度和介数中心度等.集中式算法求解这些图计算问题一般都需要问题规模的平方甚至立方以上复杂度,显然不适用于大规模图.本文旨在从分布式算法角度介绍对这些基本图计算问题具有最坏性能保证的低复杂度(线性时间)算法.此外,本文还将介绍如何通过通信复杂性理论证明分布式图计算问题的下界.
中文关键词:图分析  分布式算法  分布式复杂性  通信复杂性  拥塞模型
 
Low-complexity distributed algorithms on large-scale graphs:A brief review
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阅读器

您是本站第 635127 位访问者
版权所有:南京信息工程大学期刊社《南京信息工程大学学报》编辑部     
地址:江苏南京,宁六路219号,南京信息工程大学