基于PowerGraph并行計算框架的社會網(wǎng)絡(luò)分析研究.pdf

1、圖是一種基本的數(shù)據(jù)結(jié)構(gòu)，能夠體現(xiàn)出不同實體之間的關(guān)系。在不同的應(yīng)用領(lǐng)域中，圖被廣泛用來表示十分復(fù)雜的數(shù)據(jù)，比如:社會網(wǎng)絡(luò)、蛋白質(zhì)網(wǎng)絡(luò)、運輸網(wǎng)絡(luò)、書目網(wǎng)絡(luò)以及更多其他網(wǎng)絡(luò)。如今，個人、社區(qū)、組織、國家等行動者之間的關(guān)系越來越緊密，這些關(guān)系中所蘊含的有價值的信息也隨之飛速增長，使得社會網(wǎng)絡(luò)分析的研究日趨火熱。一般而言，社會網(wǎng)絡(luò)分析是一種重要的大數(shù)據(jù)發(fā)現(xiàn)技術(shù)。當(dāng)前，擁有百萬、甚至億萬節(jié)點和邊的大規(guī)模社會網(wǎng)絡(luò)已十分普遍，為了處理和分析大規(guī)模網(wǎng)絡(luò)

2、出現(xiàn)了一些符合其計算特點的分布式圖并行計算平臺。然而，由于許多社會網(wǎng)絡(luò)分析的經(jīng)典算法都是基于單機設(shè)計的集中式算法，無法滿足大規(guī)模社會網(wǎng)絡(luò)分析的需求。因此，本文著重從社會網(wǎng)絡(luò)傳播、矩陣分解、網(wǎng)絡(luò)重構(gòu)這三方面入手，在PowerGraph圖并行計算框架下設(shè)計并實現(xiàn)并行圖數(shù)據(jù)分析算法。本文主要完成了以下幾個方面的工作:
　　1)基于PowerGraph的并行傳播算法
　　病毒的蔓延、信息的擴散等，都可以看成是服從某種規(guī)律的網(wǎng)絡(luò)傳播行

3、為。通過傳播模型，可以模仿這些傳播行為，有助于人們理解傳播機制。傳播模型有很多種，對不同的病毒或信息，適用的傳播模型也不相同，經(jīng)典的傳播模型有SIS、SIR、SIRS、SEIR。本文基于PowerGraph提出面向SEIR模型的并行傳播算法PSA-SEIR(ParallelSpreading Algorithm for SEIR Model)。經(jīng)實驗驗證，仿真結(jié)果與SEIR模型的傳播趨勢相符，同時分析了算法的可擴展性。
　　2)基

4、于PowerGraph的并行矩陣分解(SVD++）算法
　　在社會網(wǎng)絡(luò)分析中，矩陣分解是常見的方法。由于許多網(wǎng)絡(luò)都可以抽象為矩陣的形式，社會網(wǎng)絡(luò)分析的算法可以以矩陣計算的方式實現(xiàn)。因此，了解并實現(xiàn)對大規(guī)模稀疏矩陣的分解，能夠解決許多現(xiàn)實問題（如:電影推薦）。基于此，改進了并行SVD++算法，基于PowerGraph提出學(xué)習(xí)率可調(diào)的并行SVD++算法LRA-PSVD++(LearningRate Adjustment Paralle

5、l SVD++ Algorithm)。經(jīng)實驗驗證，LRA-PSVD++提高了算法精度，此外，實驗證明了算法具有可擴展性。
　　3)基于PowerGraph的并行重構(gòu)算法
　　網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)與其許多基本特征有很大關(guān)系。同配性是網(wǎng)絡(luò)宏觀拓?fù)涞囊粋€重要特征，同配性的改變意味著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的改變。通過網(wǎng)絡(luò)重構(gòu)，構(gòu)造出具有不同同配系數(shù)的網(wǎng)絡(luò)，有助于分析同配性對網(wǎng)絡(luò)其他特征（如:傳播特征、魯棒性）的影響?；诖耍栽鰪娋W(wǎng)絡(luò)同配性為目標(biāo)，