自20世紀(jì)80年代開始,復(fù)雜系統(tǒng)的研究逐漸興起,它被認(rèn)為是解決各個領(lǐng)域研究面臨的困難的一個重要突破點。而復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜系統(tǒng)的一個重要工具,如物流運輸、道路規(guī)劃、社交網(wǎng)絡(luò)、生物研究等問題在研究的過程中,都可以抽象成由邊和頂點組成的復(fù)雜網(wǎng)絡(luò),借助于復(fù)雜網(wǎng)絡(luò)的相關(guān)技術(shù)對其進(jìn)行研究。但系統(tǒng)中基本單元常常達(dá)到成千上萬甚至是數(shù)以億計,這就使得復(fù)雜網(wǎng)絡(luò)的研究不得不借助于高效的計算工具來解決實時的、規(guī)模足夠大的計算問題。分布式計算技術(shù)是現(xiàn)在最成熟、應(yīng)用最廣、最可行的計算加速技術(shù)之一。因此研究復(fù)雜網(wǎng)絡(luò)的分布式計算技術(shù)具有十分重要的意義。在做分布式計算之前,需要將原始復(fù)雜網(wǎng)絡(luò)劃分成若干個子網(wǎng)絡(luò),保證各個子網(wǎng)絡(luò)規(guī)模相對均衡和網(wǎng)絡(luò)間的通信開銷最小化是分布式計算性能好壞的關(guān)鍵。圖劃分技術(shù)就是解決這一問題的有效手段。圖劃分算法按照劃分方式的不同,可以分為點劃分算法和邊劃分算法。數(shù)據(jù)量的快速增長對圖劃分算法的劃分質(zhì)量和劃分效率提出了新的要求。本文主要工作體現(xiàn)在以下方面:（1）針對當(dāng)前點劃分算法劃分質(zhì)量較低的問題,本文提出了基于滑動窗口的流式圖劃分模型（Graph Win）,該模型通過引入滑動窗口機制,根據(jù)當(dāng)前劃... 

【文章來源】：重慶大學(xué)重慶市 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：58 頁

【學(xué)位級別】：碩士

【部分圖文】：

圖1.1分布式環(huán)境下的圖劃分算法研究背景Fig.1.1Streamingpartitioningmodel

結(jié)果割邊率比較大。Grid算法[17]、DBH算法[18]、HDRF算法[19]都屬于此類算法。②當(dāng)前邊劃分算法仍存在效率低的問題。邊劃分算法雖然使用到圖數(shù)據(jù)的其他局部信息，能夠獲得較好的劃分結(jié)果，但該類算法由于使用啟發(fā)式算法在全局圖數(shù)據(jù)上尋找較優(yōu)劃分方案，計算時間復(fù)雜度比較大。例如，使用Metis算法對超過14億條邊的Twitter數(shù)據(jù)集做劃分時，劃分后的結(jié)果割邊率為35.96%，但劃分時間卻高達(dá)8.5小時[23]，這在許多要求實時響應(yīng)的應(yīng)用場景下是無法容忍的。所以如何提高邊劃分算法的劃分效率是當(dāng)前亟待解決的問題。圖1.2各類算法在劃分質(zhì)量和分區(qū)劃分上的對比Fig.1.2Comparisonofvariousalgorithmsinpartitionqualityandpartitiontime1.4本文的研究內(nèi)容本文對復(fù)雜網(wǎng)絡(luò)劃分做了研究，首先調(diào)研了當(dāng)前已有的圖劃分算法，并分析了這些算法的優(yōu)缺點，其次針對現(xiàn)有算法存在的不足，提出了基于滑動窗口的流式圖劃分模型（GraphWin）和基于GPU加速的圖劃分模型（GraphGPU），并結(jié)合已有的圖劃分算法對兩個模型分別做了對比試驗。本文具體研究內(nèi)容如下：①研究了圖劃分算法的發(fā)展歷史，分析了圖劃分算法中的核心概念。之后研究了圖劃分的幾種常用算法，包括傳統(tǒng)的靜態(tài)圖劃分算法和流式圖劃分算法。針對點劃分算法和邊劃分算法存在的問題，本文分別提出了基于滑動窗口的流式圖

重慶大學(xué)碩士學(xué)位論文2圖劃分算法的相關(guān)研究82圖劃分算法的相關(guān)研究圖劃分是圖論中經(jīng)典的問題之一，它在多個領(lǐng)域中有著廣泛的應(yīng)用，例如并行計算[24]、復(fù)雜網(wǎng)絡(luò)[25-31]、道路規(guī)劃[32-35]、圖像分割[36-38]、超大規(guī)模集成電路設(shè)計[39-42]等�，F(xiàn)實中的很多問題可以抽象為圖劃分問題，圖劃分可以將原始問題分解成多個小問題，再對每個小問題分別求解，從而能夠進(jìn)一步提高處理效率。本章首先給出了圖劃分的定義，之后詳細(xì)介紹了經(jīng)典的圖劃分算法和分布式計算平臺。2.1圖劃分定義定義（割邊）：給定兩個分區(qū)Pi和Pj，其中i≠j。如果這兩個分區(qū)中的任意兩點u和v存在邊，而稱這條邊為一條割邊。{(,)|,,}ijedgeCuteuveEuPvP（2.1）定義（圖劃分）：給定圖數(shù)據(jù)G=(V,E)和一個正整數(shù)k,V是圖G的頂點集合，E是圖G的邊集合,k是分區(qū)個數(shù)。圖劃分問題就是將圖數(shù)據(jù)G劃分成k個互不相交的集合P={P1,…Pk}，每個集合稱為一個分區(qū)，同時圖劃分還需要滿足兩個重要原則:①負(fù)載均衡。盡量使劃分后各分區(qū)的頂點數(shù)目大致相同，避免因任務(wù)分配不均造成資源浪費，即使得：||1,...,iVVikk（2.2）②割邊數(shù)盡可能校分區(qū)間的割邊數(shù)量直接影響通信開銷，因為分區(qū)與分區(qū)之間的通信開銷完全取決于網(wǎng)絡(luò)，而且比分區(qū)內(nèi)的通信代價高，所以為了減少總體的通信開銷，需要優(yōu)化割邊數(shù)量，關(guān)于割邊數(shù)的優(yōu)化目標(biāo)如下：1,0((,))nijMininizeedgeCutij（2.3）圖2.1基于edge-cut劃分問題示例Fig.2.1Anexampleofpartitioningproblembasedonedge-cut

【參考文獻(xiàn)】：
期刊論文
[1]BHP:面向BSP模型的負(fù)載均衡Hash圖數(shù)據(jù)劃分[J]. 周爽,鮑玉斌,王志剛,冷芳玲,于戈,鄧超,郭磊濤.  計算機科學(xué)與探索. 2014(01)



本文編號：3299662