【摘要】 近年来大规模图分析问题在网络大数据领域发挥着重要作用.经典的图分析问题包括求图的直径、半径、围长、聚类系数、紧密中心度和介数中心度等.集中式算法求解这些图计算问题一般都需要问题规模的平方甚至立方以上复杂度,显然不适用于大规模图.本文旨在从分布式算法角度介绍对这些基本图计算问题具有最坏性能保证的低复杂度(线性时间)算法.此外,本文还将介绍如何通过通信复杂性理论证明分布式图计算问题的下界.更多还原

【Abstract】 In recent years,large-scale graph analysis has played an important role in big data computing.The classi-cal graph analysis problems include computing the graph diameter,the radius,the girth,the clustering coefficientand various centrality indices.To solve these problems,centralized algorithms generally require square or even cubictime complexity,which is obviously not applicable to large-scale graphs.In this paper,we aim to briefly review somelow 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 com-munication complexity theory.更多还原