本文選題：PowerGraph　切入點(diǎn)：社會網(wǎng)絡(luò)　出處：《河北師范大學(xué)》2017年碩士論文

【摘要】：圖是一種基本的數(shù)據(jù)結(jié)構(gòu),能夠體現(xiàn)出不同實(shí)體之間的關(guān)系。在不同的應(yīng)用領(lǐng)域中,圖被廣泛用來表示十分復(fù)雜的數(shù)據(jù),比如:社會網(wǎng)絡(luò)、蛋白質(zhì)網(wǎng)絡(luò)、運(yùn)輸網(wǎng)絡(luò)、書目網(wǎng)絡(luò)以及更多其他網(wǎng)絡(luò)。如今,個(gè)人、社區(qū)、組織、國家等行動(dòng)者之間的關(guān)系越來越緊密,這些關(guān)系中所蘊(yùn)含的有價(jià)值的信息也隨之飛速增長,使得社會網(wǎng)絡(luò)分析的研究日趨火熱。一般而言,社會網(wǎng)絡(luò)分析是一種重要的大數(shù)據(jù)發(fā)現(xiàn)技術(shù)。當(dāng)前,擁有百萬、甚至億萬節(jié)點(diǎn)和邊的大規(guī)模社會網(wǎng)絡(luò)已十分普遍,為了處理和分析大規(guī)模網(wǎng)絡(luò)出現(xiàn)了一些符合其計(jì)算特點(diǎn)的分布式圖并行計(jì)算平臺。然而,由于許多社會網(wǎng)絡(luò)分析的經(jīng)典算法都是基于單機(jī)設(shè)計(jì)的集中式算法,無法滿足大規(guī)模社會網(wǎng)絡(luò)分析的需求。因此,本文著重從社會網(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ò)傳播行為。通過傳播模型,可以模仿這些傳播行為,有助于人們理解傳播機(jī)制。傳播模型有很多種,對不同的病毒或信息,適用的傳播模型也不相同,經(jīng)典的傳播模型有SIS、SIR、SIRS、SEIR。本文基于PowerGraph提出面向SEIR模型的并行傳播算法PSA-SEIR(Parallel Spreading Algorithm for SEIR Model)。經(jīng)實(shí)驗(yàn)驗(yàn)證,仿真結(jié)果與SEIR模型的傳播趨勢相符,同時(shí)分析了算法的可擴(kuò)展性。2)基于PowerGraph的并行矩陣分解(SVD++)算法在社會網(wǎng)絡(luò)分析中,矩陣分解是常見的方法。由于許多網(wǎng)絡(luò)都可以抽象為矩陣的形式,社會網(wǎng)絡(luò)分析的算法可以以矩陣計(jì)算的方式實(shí)現(xiàn)。因此,了解并實(shí)現(xiàn)對大規(guī)模稀疏矩陣的分解,能夠解決許多現(xiàn)實(shí)問題(如:電影推薦)�；诖�,改進(jìn)了并行SVD++算法,基于PowerGraph提出學(xué)習(xí)率可調(diào)的并行SVD++算法LRA-PSVD++(Learning Rate Adjustment Parallel 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)的改變。通過網(wǎng)絡(luò)重構(gòu),構(gòu)造出具有不同同配系數(shù)的網(wǎng)絡(luò),有助于分析同配性對網(wǎng)絡(luò)其他特征(如:傳播特征、魯棒性)的影響。基于此,以增強(qiáng)網(wǎng)絡(luò)同配性為目標(biāo),在保持度序列不變的條件下提出了基于PowerGraph的并行隨機(jī)重構(gòu)算法PRRWA(Parallel Random Rewiring Algorithm)。通過實(shí)驗(yàn)對算法的可行性與可擴(kuò)展性進(jìn)行了分析。
[Abstract]:A graph is a basic data structure that can reflect the relationships between different entities.In a variety of applications, graphs are widely used to represent very complex data, such as social networks, protein networks, transport networks, bibliographic networks, and more.Nowadays, the relationship among individual, community, organization, state and other actors is getting closer and closer. The valuable information contained in these relationships is also increasing rapidly, which makes the research of social network analysis become more and more hot.Generally speaking, social network analysis is an important big data discovery technology.At present, large-scale social networks with millions, even billions of nodes and edges are very common. In order to deal with and analyze large-scale networks, there are some distributed graph parallel computing platforms which accord with its computing characteristics.However, because many classical algorithms of social network analysis are centralized algorithms based on single computer, they can not meet the needs of large-scale social network analysis.Therefore, this paper focuses on the three aspects of social network propagation, matrix decomposition and network reconstruction, and designs and implements the parallel graph data analysis algorithm under the PowerGraph graph parallel computing framework.The main work of this paper is as follows: 1) the spread of virus and information in parallel communication algorithm based on PowerGraph can be regarded as the behavior of spreading from a certain law.Through the communication model, we can imitate these communication behaviors and help people understand the communication mechanism.There are many kinds of transmission models, and the transmission models are different for different viruses or information. The classical transmission models are SISSIRS / SIRS / SEIRs.Based on PowerGraph, a parallel propagation algorithm for SEIR model, PSA-SEIR(Parallel Spreading Algorithm for SEIR Modeler, is proposed in this paper.Experimental results show that the simulation results are consistent with the propagation trend of the SEIR model. At the same time, the extensibility of the algorithm is analyzed. 2) the parallel matrix decomposition algorithm based on PowerGraph is a common method in social network analysis.Because many networks can be abstracted as matrices, the algorithm of social network analysis can be realized by matrix calculation.Therefore, understanding and implementing the decomposition of large sparse matrices can solve many practical problems (such as: film recommendation).Based on this, the parallel SVD algorithm is improved, and the LRA-PSVD Rate Adjustment Parallel SVD algorithm with adjustable learning rate is proposed based on PowerGraph.Experimental results show that LRA-PSVD improves the accuracy of the algorithm. In addition, it is proved that the algorithm is extensible. 3) the topological structure of parallel reconstruction algorithm network based on PowerGraph is closely related to its many basic characteristics.Homogeneity is an important feature of network macro topology, and the change of homogeneity means the change of network topology.Through network reconstruction, a network with different matching coefficients is constructed, which is helpful to analyze the influence of homogeneity on other features of the network, such as propagation characteristics and robustness.Based on this, a parallel random reconstruction algorithm based on PowerGraph, PRRWA(Parallel Random Rewiring algorithm, is proposed to enhance the network homogeneity under the condition of invariant degree sequence.The feasibility and expansibility of the algorithm are analyzed through experiments.
【學(xué)位授予單位】：河北師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5;TP311.13

【相似文獻(xiàn)】

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

1 錢少先;關(guān)于并行計(jì)算的若干問題[J];安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2001年02期

2 胡霞;;并行計(jì)算如何用于科學(xué)問題研究[J];科技資訊;2009年27期

3 李人憲,楊忠超;流場有限元分析的并行計(jì)算[J];應(yīng)用力學(xué)學(xué)報(bào);2002年02期

4 王琥,李光耀,鐘志華;有限元并行計(jì)算中網(wǎng)格自動(dòng)分區(qū)的優(yōu)化[J];工程力學(xué);2005年S1期

5 鄭敏娟;賀炎;;未來的并行計(jì)算[J];中國科技信息;2007年12期

6 張軍;譚俊杰;任登鳳;;二維含動(dòng)邊界流場的并行計(jì)算[J];河海大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

7 曹偉;;并行計(jì)算基礎(chǔ)和實(shí)際應(yīng)用[J];遼寧師專學(xué)報(bào)(自然科學(xué)版);2008年03期

8 陳國良;孫廣中;徐云;龍柏;;并行計(jì)算的一體化研究現(xiàn)狀與發(fā)展趨勢[J];科學(xué)通報(bào);2009年08期

9 王琳;魯晶晶;殷克功;;關(guān)于并行計(jì)算在軟件發(fā)展下的研究分析[J];科技信息;2009年14期

10 劉俊莉;王楚斌;林曉銳;司徒祝坤;;并行計(jì)算實(shí)驗(yàn)平臺的研究與實(shí)現(xiàn)[J];科技信息;2009年22期

相關(guān)會議論文 前10條

1 黃宇光;;整體同步并行計(jì)算方法的現(xiàn)狀與發(fā)展[A];信息科學(xué)與微電子技術(shù):中國科協(xié)第三屆青年學(xué)術(shù)年會論文集[C];1998年

2 羅文彩;陳小前;;并行計(jì)算的多方法優(yōu)化協(xié)作[A];第二十四屆中國控制會議論文集（上冊）[C];2005年

3 左風(fēng)麗;莫?jiǎng)t堯;葉文華;;計(jì)算流體三維分裂格式的高效并行計(jì)算[A];中國工程物理研究院科技年報(bào)（2003）[C];2003年

4 王欣;李志山;張志遠(yuǎn);;并行計(jì)算在彈塑性時(shí)程分析中的應(yīng)用[A];信息化推動(dòng)工程建設(shè)工業(yè)化——第四屆工程建設(shè)計(jì)算機(jī)應(yīng)用創(chuàng)新論壇論文集[C];2013年

5 張理濤;黃廷祝;谷同祥;左憲禹;;一種適合于分布式并行計(jì)算改進(jìn)的平方共軛殘差法[A];2008年全國開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會議論文集(下冊)[C];2008年

6 胡金初;;并行計(jì)算中的任務(wù)分配算法[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2005年

7 宋庭新;李慧;;面向服務(wù)的有限元并行計(jì)算網(wǎng)格系統(tǒng)設(shè)計(jì)[A];湖北省機(jī)械工程學(xué)會設(shè)計(jì)與傳動(dòng)學(xué)會、武漢機(jī)械設(shè)計(jì)與傳動(dòng)學(xué)會2008年學(xué)術(shù)年會論文集（2）[C];2008年

8 裘懿勇;徐斌;劉曉明;;并行計(jì)算作業(yè)調(diào)度系統(tǒng)的架構(gòu)及應(yīng)用[A];第十四屆中國科協(xié)年會第5分會場：綠色船舶與海洋裝備創(chuàng)新發(fā)展及產(chǎn)業(yè)化論壇論文集[C];2012年

9 裘懿勇;徐斌;劉曉明;;并行計(jì)算作業(yè)調(diào)度系統(tǒng)的架構(gòu)及應(yīng)用[A];2012年MIS/S&A學(xué)術(shù)交流會議論文集[C];2012年

10 肖保國;楊順華;邢建文;趙慧勇;;當(dāng)?shù)刈赃m應(yīng)建表方法在煤油超燃發(fā)動(dòng)機(jī)并行計(jì)算中的應(yīng)用[A];第十四屆全國激波與激波管學(xué)術(shù)會議論文集（下冊）[C];2010年

相關(guān)重要報(bào)紙文章 前10條

1 軼嘉;英特爾全球首個(gè)并行計(jì)算中心落戶無錫[N];人民郵電;2009年

2 曙光信息產(chǎn)業(yè)有限公司研發(fā)中心 溫鑫;并行計(jì)算任重道遠(yuǎn)[N];中國計(jì)算機(jī)報(bào);2007年

3 英特爾并行計(jì)算實(shí)驗(yàn)室研究員 TimothyMattson;并行計(jì)算:減少串行軟件[N];中國計(jì)算機(jī)報(bào);2007年

4 曙光信息產(chǎn)業(yè)有限公司研發(fā)中心 溫鑫;并行計(jì)算軟件開發(fā)概述[N];中國計(jì)算機(jī)報(bào);2007年

5 劉霞;計(jì)算能力的提升需要一場革命[N];科技日報(bào);2010年

6 安世亞太 雷先華;ANSYS高性能并行計(jì)算[N];中國航空報(bào);2005年

7 張?jiān)迫?并行計(jì)算：迎接多核時(shí)代的挑戰(zhàn)[N];計(jì)算機(jī)世界;2006年

8 本報(bào)記者 馬文方;英特爾為何要牽頭并行計(jì)算[N];中國計(jì)算機(jī)報(bào);2009年

9 英特爾 趙軍(Jun Zhao);PC機(jī)并行計(jì)算革命尚未成功[N];中國計(jì)算機(jī)報(bào);2009年

10 ;Linux下的網(wǎng)絡(luò)并行計(jì)算[N];計(jì)算機(jī)世界;2000年

相關(guān)博士學(xué)位論文 前10條

1 張雨新;改進(jìn)的MPS方法及其三維并行計(jì)算研究[D];上海交通大學(xué);2014年

2 李維山;面向領(lǐng)域應(yīng)用的空間域和頻域分解模式并行計(jì)算[D];吉林大學(xué);2016年

3 萬爛軍;面向新型異構(gòu)眾核系統(tǒng)的多設(shè)備協(xié)同并行計(jì)算關(guān)鍵技術(shù)研究[D];湖南大學(xué);2016年

4 孫安香;數(shù)值氣象預(yù)報(bào)變分同化的伴隨模式并行計(jì)算[D];中國人民解放軍國防科學(xué)技術(shù)大學(xué);2002年

5 張理論;面向氣象預(yù)報(bào)數(shù)值模式的高效并行計(jì)算研究[D];中國人民解放軍國防科學(xué)技術(shù)大學(xué);2002年

6 龍柏;并行計(jì)算平臺上的數(shù)據(jù)索引技術(shù)研究[D];中國科學(xué)技術(shù)大學(xué);2011年

7 管建和;電磁場有限元法解釋分布式并行計(jì)算的研究[D];中國地質(zhì)大學(xué)（北京）;2006年

8 劉耀儒;三維有限元并行計(jì)算及其在水利工程中的應(yīng)用[D];清華大學(xué);2003年

9 金晶;并行計(jì)算普適編程模型及系統(tǒng)架構(gòu)研究[D];北京郵電大學(xué);2012年

10 盛艷秀;多核異構(gòu)環(huán)境下通用并行計(jì)算框架關(guān)鍵技術(shù)研究[D];中國海洋大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 張康宇;基于ASAR近海風(fēng)場反演方法研究[D];浙江大學(xué);2015年

2 胡榮華;并行計(jì)算在臨近天氣預(yù)報(bào)系統(tǒng)中的應(yīng)用研究[D];華南理工大學(xué);2015年

3 嚴(yán)善楷;異構(gòu)系統(tǒng)中并行計(jì)算的動(dòng)態(tài)負(fù)載均衡技術(shù)研究[D];華南理工大學(xué);2015年

4 陳磊;基于監(jiān)控信號的多信息提取識別的并行計(jì)算方法[D];南京理工大學(xué);2015年

5 焦弘杰;CPU-GPU異構(gòu)并行計(jì)算體系的設(shè)計(jì)與實(shí)現(xiàn)[D];江蘇科技大學(xué);2015年

6 陳從江;基于面向云服務(wù)的Python并行計(jì)算的研究[D];電子科技大學(xué);2014年

7 唐吉卓;基于GPU平臺的SVD并行計(jì)算研究與實(shí)現(xiàn)[D];電子科技大學(xué);2014年

8 吳頎;GPU并行計(jì)算及其在飛行器設(shè)計(jì)中的應(yīng)用[D];北京理工大學(xué);2015年

9 李保安;基于液態(tài)食品冷凍濃縮冰晶生長機(jī)制并行計(jì)算[D];電子科技大學(xué);2013年

10 鐘承群;基于CPU/GPU異構(gòu)并行計(jì)算的OTN仿真驗(yàn)證系統(tǒng)的研究與實(shí)現(xiàn)[D];電子科技大學(xué);2015年

，

本文編號：1723655