基于AP算法的社區(qū)檢測算法及其并行化研究.pdf

1、現(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)的進(jìn)行檢測的方法叫做社區(qū)檢測(Community Detection)。社區(qū)檢測作為網(wǎng)絡(luò)分析的基本任務(wù)有助于其它網(wǎng)絡(luò)計算任務(wù)的完成，近年來有很多針對社區(qū)檢測的研究并取得了不少研究成果。

2、>　　科學(xué)技術(shù)的不斷進(jìn)步使得網(wǎng)絡(luò)的規(guī)模不斷增大，現(xiàn)有的部分社區(qū)檢測算法已經(jīng)不能勝任大規(guī)模網(wǎng)絡(luò)的社區(qū)檢測任務(wù)。另外，社區(qū)檢測問題能夠轉(zhuǎn)化為聚類問題，所以本文主要從相似性算法、聚類算法和分布式并行化計算三個方面入手對社區(qū)檢測問題進(jìn)行研究，本文的主要內(nèi)容如下：
　　1.在現(xiàn)有的一些針對網(wǎng)絡(luò)中頂點之間相似性進(jìn)行計算的算法研究中，大多數(shù)算法要么時間復(fù)雜度過高，要么沒有充分的考慮整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)?；谝陨蠁栴}，本文以隨機(jī)游走模型為基礎(chǔ)并基于

3、個性化排名算法APR(Approximate PageRank)算法，提出了一種快速的相似性計算算法，使得該算法在充分考慮網(wǎng)絡(luò)的拓?fù)淝闆r下提高網(wǎng)絡(luò)中頂點之間相似性計算的效率。
　　2.在社區(qū)檢測的聚類階段，現(xiàn)有的一些聚類算法不能夠充分的利用網(wǎng)絡(luò)中所蘊(yùn)含的信息使得檢測出來的社區(qū)質(zhì)量不高?；谝陨蠁栴}，本文提出了一種適用于針對網(wǎng)絡(luò)進(jìn)行社區(qū)檢測的半監(jiān)督聚類算法SSAP(Similarity Set basedAffinity Propa

4、gation)，該算法是基于AP(Affinity Propagation)算法的一種改進(jìn)，提高了聚類算法在迭代時的運(yùn)行效率以及整個算法的收斂速度。并結(jié)合提出的相似性計算方法，把社區(qū)檢測問題轉(zhuǎn)化成為了聚類問題。
　　3.隨著分布式計算的技術(shù)越來越成熟，比如基于Hadoop平臺的MapReduce并行化計算框架、基于內(nèi)存模型的并行化計算框架Spark等。這些分布式計算技術(shù)的出現(xiàn)使得先前不能在單機(jī)環(huán)境下完成的計算任務(wù)得以實現(xiàn)。同時，在