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

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

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

• 摘要5-6
• ABSTRACT6-10
• 第一章 緒論10-16
• 1.1 研究工作的背景與意義10-11
• 1.2 國(guó)內(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ò)簡(jiǎn)介16-17
• 2.2 網(wǎng)絡(luò)的特征17-20
• 2.3 社區(qū)檢測(cè)現(xiàn)有算法20-22
• 2.4 并行化計(jì)算框架22-26
• 2.4.1 內(nèi)存計(jì)算框架Spark22-24
• 2.4.2 圖計(jì)算模型Spark GraphX24-26
• 2.5 本章小結(jié)26-27
• 第三章 基于APR算法的相似性算法27-42
• 3.1 隨機(jī)游走模型27-28
• 3.2 基于隨機(jī)游走模型的APR算法28-35
• 3.2.1 相似性矩陣與相似性集合30-32
• 3.2.2 基于 APR 算法相似性算法32-35
• 3.3 相似性算法的并行化實(shí)現(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ū)檢測(cè)算法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ū)檢測(cè)算法45-52
• 4.2.1 因子圖模型45-47
• 4.2.2 SSAP：基于相似性集合的AP聚類算法47-52
• 4.2.3 時(shí)間復(fù)雜度分析52
• 4.3 SSAP算法的并行化實(shí)現(xiàn)52-60
• 4.3.1 算法的輸入及相似性網(wǎng)絡(luò)圖的初始化53-54
• 4.3.2 更新責(zé)任度54-56
• 4.3.3 更新可信度56-58
• 4.3.4 對(duì)社區(qū)進(jìn)行劃分58-60
• 4.4 本章小結(jié)60-61
• 第五章 實(shí)驗(yàn)及結(jié)果分析61-73
• 5.1 實(shí)驗(yàn)環(huán)境61-62
• 5.2 實(shí)驗(yàn)數(shù)據(jù)62-64
• 5.3 評(píng)價(jià)函數(shù)64-65
• 5.4 實(shí)驗(yàn)結(jié)果分析65-72
• 5.4.1 真實(shí)網(wǎng)絡(luò)上的評(píng)價(jià)結(jié)果對(duì)比65-67
• 5.4.2 人工網(wǎng)絡(luò)上的結(jié)果對(duì)評(píng)價(jià)比67-69
• 5.4.3 運(yùn)行時(shí)間和迭代次數(shù)對(duì)比69-72
• 5.5 本章小結(jié)72-73
• 第六章 全文總結(jié)與展望73-75
• 6.1 本文總結(jié)73
• 6.2 未來(lái)的工作73-75
• 致謝75-76
• 參考文獻(xiàn)76-82

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

8 陳再高;王s

本文編號(hào)：1107577