大規(guī)模分布式圖分割算法.pdf

1、隨著互聯(lián)網(wǎng)信息規(guī)模的急速膨脹，對大規(guī)模數(shù)據(jù)進行快速處理、學習和挖掘的需求也變得越來越多。在許多真實應(yīng)用比如社交網(wǎng)絡(luò)中，具有圖結(jié)構(gòu)的數(shù)據(jù)的規(guī)模也在不斷變大。因此，基于圖計算的大規(guī)模分布式（并行）機器學習框架受到了越來越多的關(guān)注。一方面，許多數(shù)據(jù)間的依賴關(guān)系可以自然地用圖來進行建模，而且許多數(shù)據(jù)本身就具有圖或網(wǎng)絡(luò)的結(jié)構(gòu)，例如社交網(wǎng)絡(luò)數(shù)據(jù)；另一方面，許多機器學習和數(shù)據(jù)挖掘的算法也可以用圖或網(wǎng)絡(luò)來建模。在基于圖計算的大規(guī)模機器學習框架中，數(shù)據(jù)以

2、圖的結(jié)構(gòu)表示。為了在這種圖結(jié)構(gòu)的數(shù)據(jù)上運行分布式（并行）機器學習或數(shù)據(jù)挖掘算法，首先必須將這些結(jié)構(gòu)化的數(shù)據(jù)分配到分布式環(huán)境中的每一臺計算機上。數(shù)據(jù)的分配會影響到算法運行期間，集群中的計算機直接的通信量和每臺計算機的負載均衡，因此會在很大程度上影響分布式算法的運行效率。圖結(jié)構(gòu)的數(shù)據(jù)分配因而在基于圖計算的大規(guī)模機器學習框架中扮演了重要的角色。理想的數(shù)據(jù)分配方式，將會在大致平衡每臺計算機之間的負載的同時，最小化集群中計算機之間的通信量。這一類

3、具有圖結(jié)構(gòu)的數(shù)據(jù)的分配問題統(tǒng)稱為圖的分割問題。為了快速求解圖分割問題，往往使用隨機化的圖分割算法。許多真實數(shù)據(jù)的圖的節(jié)點度數(shù)分布往往服從冪律分布，這樣的分布增加了數(shù)據(jù)分配的難度。近年來，研究者們提出了一些隨機化算法來求解圖分割問題。然而，現(xiàn)存的隨機化圖分割算法對于服從冪律分布的圖難以得到令人滿意的效果。此外，極少有隨機化的圖分割算法利用了圖中每個節(jié)點的度數(shù)信息。在本課題的研究將會提出新的圖分割算法，包括隨機化圖分割算法和貪心算法。本課題