隨著社交網(wǎng)絡(luò)的不斷發(fā)展,社區(qū)發(fā)現(xiàn)已經(jīng)成為復(fù)雜網(wǎng)絡(luò)領(lǐng)域的一個重要的研究熱點。若干個社區(qū)組成了一個完整的網(wǎng)絡(luò),在社區(qū)的內(nèi)部,節(jié)點之間的連接相對緊密,而社區(qū)與社區(qū)之間節(jié)點間的連接則相對松散。標簽傳播算法LPA（Label Propagation Algorithm）是社區(qū)發(fā)現(xiàn)算法中比較優(yōu)秀的算法。它的線性的時間復(fù)雜度是它的一大優(yōu)勢。雖然LPA有很多的優(yōu)點,但是缺點也是非常明顯的。由于標簽的隨機選擇,LPA不能保證每次結(jié)果的一致性;此外,在多次迭代之后,可能會出現(xiàn)大的社區(qū)將小社區(qū)吞并的現(xiàn)象。結(jié)合以上內(nèi)容,本文在LPA的基礎(chǔ)上改進擴展出了兩個算法,具體的研究成果如下所示:（1）LPA的優(yōu)化改進LPA算法不包含任何參數(shù),主要對標簽傳播及更新進行優(yōu)化。在基于概率和相似度的標簽傳播算法 PSLPA（Probability and Similarity based Label Propagation Algorithm）中,結(jié)合節(jié)點間的概率以及相似度,并在標簽傳播的過程中使用了自適應(yīng)標簽選擇的方式對節(jié)點標簽進行更新。在基于節(jié)點權(quán)重和隨機游走的標簽傳播算法WRWILPA（Weightand Random ... 

【文章來源】：南京信息工程大學(xué)江蘇省

【文章頁數(shù)】：58 頁

【學(xué)位級別】：碩士

【部分圖文】：

圖２－１標簽震蕩７Ｋ意圖??除此之外，簽播法可能出現(xiàn)“”區(qū)，當一區(qū)簽己經(jīng)

（ｃ）?２－ｓｈｅｌｌ中的節(jié)點?（ｄ）?３－ｓｈｅｌ丨中的節(jié)點??圖３－１?—個可分解為３個ｓｈｅｌｌ的網(wǎng)絡(luò)示意圖??對于圖３－１?（ａ）中的網(wǎng)絡(luò)圖，各個節(jié)點所屬的ｓｈｅｌｌ以及其ｉｔｅｒａｔｉｏｎ值如表３－１所?表分解后節(jié)點所屬ｓｈｅｌｌ及ｉｔｅｍｔｉｙｎ值?節(jié)點?ｉｔｅｒａｔｉｏｎ?值???一?１－ｓｈｅｌｌ?￣９，１０，１１，１２，１３，１５，１７，１８，１９，２０＂?１?一?１－ｓｈｅｌｌ?１４，１６?２??一?２－ｓｈｅｌｌ?５，６，７，８?—?１?￣?３－ｓｈｅｌｌ?１，２，３，４?１?．２基于概率和相似度的標簽傳播方法??在傳統(tǒng)的標簽傳播算法中，鄰居節(jié)點之間并沒有什么差異性，都是被同等對待。實際情況不是這樣，不同的鄰居節(jié)點可能對該節(jié)點有不同的影響力，所以為每一賦予一個權(quán)重是很合理的選擇。ＰＳＬＰＡ根據(jù)以下的步驟來進行節(jié)點標簽的選擇以

火ｑ）和火《７．）分別表示節(jié)點ｑ和％的度，ｉＮＴｈ）表示節(jié)點ｎ，．的所有鄰居節(jié)點集??合，使用／ＣＡ＾）表示節(jié)點ｑ的鄰居索引，從式子中可以看出／ａｖ（？ｆ）ｅ［ｏ，ｉ］。??將圖３．２作為例子，從圖中可以看出節(jié)點１，９，?１４，?１７是度為１的葉子節(jié)點，節(jié)點１??只有一個鄰居節(jié)點，為節(jié)點６，所以火遍歷圖中的１７個節(jié)點，可??以得到節(jié)點１０及其所有鄰居的度之和為最大的２３，所以＾〇＼＾）＝５／２３?＝?０．２２，即節(jié)點??１的鄰居索引值為０．２２；依次計算其余葉子節(jié)點，可以得到ＪＣＡＴ（％）－４／２３?＝?０．１７，??７〇＼＾４）＝７／２３?＝?０．３０，?７〇＼＾７）＝２／２３?＝?０．０９。從結(jié)果中可以清楚的看到，鄰居索引／ＣＡＴ??值可以有效的區(qū)分擁有相同度的節(jié)點。??定義２．給定一個社交網(wǎng)絡(luò)Ｇ（Ｖ，Ｅ），通過Ｋ－Ｓｈｅｌｌ分解方法，每個節(jié)點都被賦予一個??馬值。對于每一輪Ｋ－Ｓｈｅｌｌ分解，假設(shè)迭代次數(shù)為／？，并且節(jié)點ｑ是在第ｎ次迭代中刪??除的，這里因此位置索引可以計算為表３－１列出了整個Ｋ－Ｓｈｅｌｌ分解??的過程。結(jié)合公式（１）

【參考文獻】：
期刊論文
[1]基于夾角余弦的證據(jù)組合方法[J]. 胡嘉驥,李新德,王豐羽.  模式識別與人工智能. 2015(09)
[2]Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J]. 武志昊,林友芳,Steve Gregory,萬懷宇School of Computer and Information Technology,Beijing Jiaotong University,田盛豐.  Journal of Computer Science & Technology. 2012(03)

碩士論文
[1]基于SCAN算法的社區(qū)發(fā)現(xiàn)算法研究[D]. 王耀.南京信息工程大學(xué) 2016



本文編號：3379346