華強(qiáng)勝 艾明 錢立祥 于東曉 石宣化 金海

摘要 近年來大規(guī)模圖分析問題在網(wǎng)絡(luò)大數(shù)據(jù)領(lǐng)域發(fā)揮著重要作用.經(jīng)典的圖分析問題包括求圖的直徑、半徑、圍長、聚類系數(shù)、緊密中心度和介數(shù)中心度等.集中式算法求解這些圖計算問題一般都需要問題規(guī)模的平方甚至立方以上復(fù)雜度，顯然不適用于大規(guī)模圖.本文旨在從分布式算法角度介紹對這些基本圖計算問題具有最壞性能保證的低復(fù)雜度（線性時間）算法.此外，本文還將介紹如何通過通信復(fù)雜性理論證明分布式圖計算問題的下界.

關(guān)鍵詞 圖分析；分布式算法；分布式復(fù)雜性；通信復(fù)雜性；擁塞模型

中圖分類號TP301.5；TP301.6；TP338.8

文獻(xiàn)標(biāo)志碼A