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

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

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

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