基于局部鄰域的最大密度子圖檢測(cè)方法研究與實(shí)現(xiàn).pdf

1、現(xiàn)實(shí)世界存在著大量包含多類對(duì)象、對(duì)象之間存在多種關(guān)系的復(fù)雜網(wǎng)絡(luò)，這些網(wǎng)絡(luò)表現(xiàn)出的基于平均密度的聚集效應(yīng)為我們研究對(duì)象之間的深層次關(guān)系提供機(jī)會(huì)。最大密度子圖檢測(cè)是一個(gè)重要的圖挖掘問題，可應(yīng)用在計(jì)算機(jī)、生物科學(xué)、社會(huì)學(xué)和物理學(xué)等多個(gè)學(xué)科領(lǐng)域。該問題的目的是求解給定圖中，結(jié)點(diǎn)之間連邊相對(duì)密切的子圖，使得子圖的平均密度達(dá)到最大。對(duì)于提出改進(jìn)的高準(zhǔn)確率、穩(wěn)定性算法和高效率計(jì)算策略是本文的關(guān)鍵。
　　本文提出一種基于局部廣度優(yōu)先擴(kuò)張與收縮的方

2、法來檢測(cè)給定圖中的最大密度子圖。本算法主要分為三部分：擴(kuò)張、收縮和下一次迭代。首先，選定圖中的最優(yōu)結(jié)點(diǎn)，并從該結(jié)點(diǎn)出發(fā)做局部廣度優(yōu)先擴(kuò)張，直到?jīng)]有結(jié)點(diǎn)可進(jìn)行擴(kuò)張；其次，對(duì)擴(kuò)張所得到的擴(kuò)張結(jié)點(diǎn)集合進(jìn)行收縮，從而得出當(dāng)前迭代過程的局部最大密度子圖；再次，在該局部最大密度子圖相對(duì)于原圖的補(bǔ)圖上不斷進(jìn)行上述迭代，直至補(bǔ)圖為空；每次迭代結(jié)束，保留平均密度相對(duì)較大的密度子圖，最終保留的子圖即為所求原圖的最大密度子圖。進(jìn)一步地，針對(duì)大規(guī)模圖上的最大密

3、度子圖挖掘所遇到的困難，本文采用分治策略，提出廣度搜索結(jié)合最小割的圖分割方法將大圖分割成多個(gè)子圖，然后采用單機(jī)和集群求解top-K最大密度子圖。在單機(jī)中，使用平行滑動(dòng)分片策略，將分片逐個(gè)加載進(jìn)內(nèi)存進(jìn)行計(jì)算，將該分片求解得到的最大密度子圖寫回硬盤覆蓋原分片；對(duì)于集群，本文分別在Hadoop平臺(tái)上完成基于MapReduce框架的算法實(shí)現(xiàn)和在Giraph平臺(tái)上完成基于BSP框架的算法實(shí)現(xiàn)。
　　實(shí)驗(yàn)表明，本文所提出的局部廣度優(yōu)先擴(kuò)張與收