本文關(guān)鍵詞：基于AP算法的社區(qū)檢測算法及其并行化研究

  更多相關(guān)文章： 社區(qū)檢測 相似性 SSAP算法 Spark 并行化

【摘要】：現(xiàn)實生活中很多系統(tǒng)結(jié)構(gòu)都能抽象成網(wǎng)絡(luò),比如關(guān)系網(wǎng)絡(luò)、新陳代謝網(wǎng)絡(luò)、電子郵件通信網(wǎng)絡(luò)、移動電話網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)能夠根據(jù)內(nèi)部的相互作用表現(xiàn)出某些結(jié)構(gòu)特征,其中社區(qū)結(jié)構(gòu)(Community Structure)是這類網(wǎng)絡(luò)中一個重要的特征,對網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)的進行檢測的方法叫做社區(qū)檢測(Community Detection)。社區(qū)檢測作為網(wǎng)絡(luò)分析的基本任務(wù)有助于其它網(wǎng)絡(luò)計算任務(wù)的完成,近年來有很多針對社區(qū)檢測的研究并取得了不少研究成果�？茖W技術(shù)的不斷進步使得網(wǎng)絡(luò)的規(guī)模不斷增大,現(xiàn)有的部分社區(qū)檢測算法已經(jīng)不能勝任大規(guī)模網(wǎng)絡(luò)的社區(qū)檢測任務(wù)。另外,社區(qū)檢測問題能夠轉(zhuǎn)化為聚類問題,所以本文主要從相似性算法、聚類算法和分布式并行化計算三個方面入手對社區(qū)檢測問題進行研究,本文的主要內(nèi)容如下:1.在現(xiàn)有的一些針對網(wǎng)絡(luò)中頂點之間相似性進行計算的算法研究中,大多數(shù)算法要么時間復雜度過高,要么沒有充分的考慮整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)�；谝陨蠁栴},本文以隨機游走模型為基礎(chǔ)并基于個性化排名算法APR(Approximate Page Rank)算法,提出了一種快速的相似性計算算法,使得該算法在充分考慮網(wǎng)絡(luò)的拓撲情況下提高網(wǎng)絡(luò)中頂點之間相似性計算的效率。2.在社區(qū)檢測的聚類階段,現(xiàn)有的一些聚類算法不能夠充分的利用網(wǎng)絡(luò)中所蘊含的信息使得檢測出來的社區(qū)質(zhì)量不高�；谝陨蠁栴},本文提出了一種適用于針對網(wǎng)絡(luò)進行社區(qū)檢測的半監(jiān)督聚類算法SSAP(Similarity Set based Affinity Propagation),該算法是基于AP(Affinity Propagation)算法的一種改進,提高了聚類算法在迭代時的運行效率以及整個算法的收斂速度。并結(jié)合提出的相似性計算方法,把社區(qū)檢測問題轉(zhuǎn)化成為了聚類問題。3.隨著分布式計算的技術(shù)越來越成熟,比如基于Hadoop平臺的Map Reduce并行化計算框架、基于內(nèi)存模型的并行化計算框架Spark等。這些分布式計算技術(shù)的出現(xiàn)使得先前不能在單機環(huán)境下完成的計算任務(wù)得以實現(xiàn)。同時,在社區(qū)檢測任務(wù)中,由于面臨的網(wǎng)絡(luò)規(guī)模越來越龐大,至此,本文在Spark框架下對所提出的社區(qū)檢測算法進行了并行化實現(xiàn),利用分布式并行化的優(yōu)勢使得該算法能夠?qū)Υ笠?guī)模的網(wǎng)絡(luò)進行社區(qū)檢測。
【關(guān)鍵詞】：社區(qū)檢測 相似性 SSAP算法 Spark 并行化
【學位授予單位】：電子科技大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP311.13;TP393.06
【目錄】：

• 摘要5-6
• ABSTRACT6-10
• 第一章 緒論10-16
• 1.1 研究工作的背景與意義10-11
• 1.2 國內(nèi)外研究現(xiàn)狀11-14
• 1.3 本文的主要工作14
• 1.4 本論文的結(jié)構(gòu)安排14-15
• 1.5 本章小結(jié)15-16
• 第二章 相關(guān)理論與技術(shù)16-27
• 2.1 網(wǎng)絡(luò)簡介16-17
• 2.2 網(wǎng)絡(luò)的特征17-20
• 2.3 社區(qū)檢測現(xiàn)有算法20-22
• 2.4 并行化計算框架22-26
• 2.4.1 內(nèi)存計算框架Spark22-24
• 2.4.2 圖計算模型Spark GraphX24-26
• 2.5 本章小結(jié)26-27
• 第三章 基于APR算法的相似性算法27-42
• 3.1 隨機游走模型27-28
• 3.2 基于隨機游走模型的APR算法28-35
• 3.2.1 相似性矩陣與相似性集合30-32
• 3.2.2 基于 APR 算法相似性算法32-35
• 3.3 相似性算法的并行化實現(xiàn)35-41
• 3.3.1 輸入文件格式35-36
• 3.3.2 網(wǎng)絡(luò)的初始化36-38
• 3.3.3 更新排名向量和剩余向量38-40
• 3.3.4 相似性的規(guī)范化及輸出40-41
• 3.4 本章小結(jié)41-42
• 第四章 SSAP：一種基于AP算法的社區(qū)檢測算法42-61
• 4.1 AP聚類算法42-45
• 4.1.1 算法的輸入43-44
• 4.1.2 結(jié)果的劃分44
• 4.1.3 算法的流程44-45
• 4.2 一種基于AP算法的社區(qū)檢測算法45-52
• 4.2.1 因子圖模型45-47
• 4.2.2 SSAP：基于相似性集合的AP聚類算法47-52
• 4.2.3 時間復雜度分析52
• 4.3 SSAP算法的并行化實現(xiàn)52-60
• 4.3.1 算法的輸入及相似性網(wǎng)絡(luò)圖的初始化53-54
• 4.3.2 更新責任度54-56
• 4.3.3 更新可信度56-58
• 4.3.4 對社區(qū)進行劃分58-60
• 4.4 本章小結(jié)60-61
• 第五章 實驗及結(jié)果分析61-73
• 5.1 實驗環(huán)境61-62
• 5.2 實驗數(shù)據(jù)62-64
• 5.3 評價函數(shù)64-65
• 5.4 實驗結(jié)果分析65-72
• 5.4.1 真實網(wǎng)絡(luò)上的評價結(jié)果對比65-67
• 5.4.2 人工網(wǎng)絡(luò)上的結(jié)果對評價比67-69
• 5.4.3 運行時間和迭代次數(shù)對比69-72
• 5.5 本章小結(jié)72-73
• 第六章 全文總結(jié)與展望73-75
• 6.1 本文總結(jié)73
• 6.2 未來的工作73-75
• 致謝75-76
• 參考文獻76-82

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 吳正娟;職為梅;楊勇;范明;;并行化的粒子群技術(shù)[J];微計算機信息;2009年36期

2 齊書陽;;迎接并行化的明天[J];軟件世界;2009年06期

3 曹琳,楊學軍,金國華;兩種并行化機制的分析[J];計算機研究與發(fā)展;1993年09期

4 金國華，，陳福接;并行化技術(shù)與工具[J];計算機研究與發(fā)展;1996年07期

5 蔡立志,童維勤,廖文昭;序列拼裝程序的并行化研究與實現(xiàn)[J];計算機工程與應(yīng)用;2003年14期

6 王偉;潘建偉;;有限差分法的并行化計算實現(xiàn)[J];電腦知識與技術(shù);2008年07期

7 程錦松;;迭代法的并行化[J];安徽大學學報(自然科學版);1997年03期

8 陳再高;王s

本文編號：1107577