基于PowerGraph并行計算框架的社會網絡分析研究.pdf

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

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

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

4、于PowerGraph的并行矩陣分解(SVD++）算法
　　在社會網絡分析中，矩陣分解是常見的方法。由于許多網絡都可以抽象為矩陣的形式，社會網絡分析的算法可以以矩陣計算的方式實現。因此，了解并實現對大規(guī)模稀疏矩陣的分解，能夠解決許多現實問題（如:電影推薦）?；诖耍倪M了并行SVD++算法，基于PowerGraph提出學習率可調的并行SVD++算法LRA-PSVD++(LearningRate Adjustment Paralle

5、l SVD++ Algorithm)。經實驗驗證，LRA-PSVD++提高了算法精度，此外，實驗證明了算法具有可擴展性。
　　3)基于PowerGraph的并行重構算法
　　網絡的拓撲結構與其許多基本特征有很大關系。同配性是網絡宏觀拓撲的一個重要特征，同配性的改變意味著網絡拓撲結構的改變。通過網絡重構，構造出具有不同同配系數的網絡，有助于分析同配性對網絡其他特征（如:傳播特征、魯棒性）的影響?；诖耍栽鰪娋W絡同配性為目標，