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

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

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

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

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

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