大规模图中低复杂度分布式算法浅析

摘要

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