【摘要】：大規(guī)模復(fù)雜網(wǎng)絡(luò)下使用并行圖計(jì)算的意義在于,將并行計(jì)算、圖、社區(qū)劃分算法相融合使得社交網(wǎng)絡(luò)社區(qū)劃分更精準(zhǔn)、更快速、更可靠等,該研究對社區(qū)群體行為分析、社區(qū)情感分析、推薦系統(tǒng)、廣告定向投放及社會(huì)維穩(wěn)等有廣泛的實(shí)際應(yīng)用意義。通過采用改進(jìn)的譜聚類算法并實(shí)行并行化,在改進(jìn)算法中主要使用三角模型的方式計(jì)算社交網(wǎng)絡(luò)節(jié)點(diǎn)間的相似性,從而改變了譜聚類鄰接矩陣構(gòu)造過程。最后,使用社區(qū)劃分評價(jià)指標(biāo)模塊度度改進(jìn)算法的效率進(jìn)行了度量,并將該算法與目前較好的社區(qū)劃分算法做了對比,在對比中體現(xiàn)出本文算法在高效、準(zhǔn)確、可擴(kuò)展方面的優(yōu)勢。研究表明社區(qū)劃分特點(diǎn)是社區(qū)內(nèi)緊密性較高,社區(qū)間緊密型較低,在大規(guī)模網(wǎng)絡(luò)圖中,社區(qū)劃分后依然存在社區(qū)重疊區(qū)域較多的問題,考慮到這些因素可能導(dǎo)致社區(qū)劃分的準(zhǔn)確度降低,引入基于子圖劃分的聚類算法來檢測重疊社區(qū),從而優(yōu)化改進(jìn)的譜聚類算法在社區(qū)劃分中的準(zhǔn)確度并結(jié)合并行計(jì)算方式,綜合以上方式進(jìn)一步確定了本文提出方法的高效性、準(zhǔn)確性、可靠性特征。通過結(jié)合大規(guī)模數(shù)據(jù)集Twitter數(shù)據(jù)集和Stanford Large Network Dataset Collection測試數(shù)據(jù)集進(jìn)行相關(guān)實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,本文提出的方法具有可擴(kuò)展性,能快速、準(zhǔn)確的對大規(guī)模復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。
【圖文】：

圖 3. 1 社交網(wǎng)絡(luò)結(jié)構(gòu)采樣圖值的規(guī)范化拉普拉斯是譜聚類算法思想下重要的一個(gè)環(huán)值，基于三角模型求節(jié)點(diǎn)對相似性鄰接矩陣構(gòu)造。節(jié)點(diǎn)對相似性通過中，通過相似距離來衡量的不可定點(diǎn)相似性不可控性。通過這樣的計(jì)，避免了人為誤差，整個(gè)節(jié)點(diǎn)相似的數(shù)據(jù)可靠性。雖然通過三角模矩陣的構(gòu)建，但提出了完全基于網(wǎng)較強(qiáng)相似性，社區(qū)之間相似性低，

輸出：網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)集的 k 個(gè)子圖；4 規(guī)范化 Laplace 矩陣， = 12 12；5 并行化改進(jìn)的譜聚類a = λ ，獲得前 k 個(gè)最大特征值的特征向量  k；6 將前 k 個(gè)最大特征值的特征向量為列向量構(gòu)建矩陣 n k；7 令-i k = ￠表示 V 的第 i 個(gè)行向量；8 將原來 n*n 的矩陣，降維到 n*k 維矩陣；9 并行化 k-means 算法，對 n*k 矩陣進(jìn)行聚類，得到 k 個(gè)類群分別為： k；10 根據(jù)聚類的 k 群體，可視化網(wǎng)絡(luò)結(jié)構(gòu)。3.3.3 基于 Spark 的并行化實(shí)現(xiàn)基于 Spark 下的三角模型計(jì)算節(jié)點(diǎn)對相似性權(quán)值，三角模型在單機(jī)計(jì)算下的時(shí)間復(fù)雜度為(￠n )，在并行化下時(shí)間復(fù)雜得到了很大的改進(jìn)，，利用 Spark 基于內(nèi)存迭代計(jì)算的優(yōu)勢[17]，將大規(guī)模數(shù)據(jù)集使用分而治之的思想進(jìn)行處理，三角模型并行化如圖 3.2 所示。
【學(xué)位授予單位】：重慶郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP301.6;O157.5

【參考文獻(xiàn)】

相關(guān)期刊論文 前3條

1 駱志剛;丁凡;蔣曉舟;石金龍;;復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法研究新進(jìn)展[J];國防科技大學(xué)學(xué)報(bào);2011年01期

2 王愛平;張功營;劉方;;EM算法研究與應(yīng)用[J];計(jì)算機(jī)技術(shù)與發(fā)展;2009年09期

3 蔡曉妍;戴冠中;楊黎斌;;譜聚類算法綜述[J];計(jì)算機(jī)科學(xué);2008年07期

本文編號：2689054