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

• 作者: 于东晓 华强胜 石宣化 艾明 金海 钱立祥
• 来源期刊: 南京信息工程大学学报
• 学科: 工学
• 关键词: 图分析 分布式算法 分布式复杂性 通信复杂性 拥塞模型
• 年，卷（期）: 2017,（5）
• 所属期刊栏目: 研究性论文
• 页码范围: 533-543
• 页数: 11页
• 分类号: TP301.5|TP301.6|TP338.8
• 字数: 12133字
• 语种: 中文
• DOI: 10.13878/j.cnki.jnuist.2017.05.012

摘要

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