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

华强胜 艾明 钱立祥 于东晓 石宣化 金海

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

关键词 图分析；分布式算法；分布式复杂性；通信复杂性；拥塞模型

中图分类号TP301.5；TP301.6；TP338.8

文献标志码A