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

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

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

【參考文獻】

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

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

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

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

本文編號：2689054