自適應(yīng)標(biāo)簽傳播算法的研究及其應(yīng)用實(shí)現(xiàn).pdf

1、近幾年，互聯(lián)網(wǎng)飛速發(fā)展而產(chǎn)生了海量的數(shù)據(jù)，對(duì)海量數(shù)據(jù)的處理催生了數(shù)據(jù)挖掘技術(shù)。而社區(qū)發(fā)現(xiàn)技術(shù)是數(shù)據(jù)挖掘的重要組成部分，已經(jīng)成為眾多學(xué)者的研究熱點(diǎn)。社區(qū)發(fā)現(xiàn)算法可以發(fā)現(xiàn)存在于各種網(wǎng)絡(luò)中的潛在社區(qū)，從而可以對(duì)不同的社區(qū)進(jìn)行進(jìn)一步的挖掘分析。但是社區(qū)的多樣性，復(fù)雜性所帶來(lái)的龐大數(shù)據(jù)量也為社區(qū)發(fā)現(xiàn)帶來(lái)諸多不便，因此快速收斂的社區(qū)發(fā)現(xiàn)算法顯的越來(lái)越重要?；跇?biāo)簽傳播的社區(qū)挖掘算法以其較低的時(shí)間復(fù)雜性而得到很大重視。有人在標(biāo)簽傳播算法的基礎(chǔ)上，提出

2、了衰減標(biāo)簽傳播算法以及可以進(jìn)行重疊社區(qū)發(fā)現(xiàn)的SLPA(Speaker-Listener label propagation algorithm)算法。但是SLPA算法容易產(chǎn)生怪獸社區(qū)，而衰減標(biāo)簽傳播算法容易對(duì)社區(qū)進(jìn)行過(guò)度分割。
　　本文在 SLPA算法和衰減標(biāo)簽傳播算法的基礎(chǔ)上，結(jié)合兩個(gè)算法的優(yōu)點(diǎn)，提出了自適應(yīng)控制距離的標(biāo)簽傳播算法。該算法的主要特點(diǎn)有：
　?、賹?duì)每一個(gè)歷史標(biāo)簽限定其傳播距離。標(biāo)簽每傳播一次它的傳播距離就減少

3、一，直到傳播距離為零，此時(shí)該標(biāo)簽再也不能向其鄰居節(jié)點(diǎn)傳播，這樣就阻止了標(biāo)簽的無(wú)限傳播，減少怪獸社區(qū)產(chǎn)生的可能性；
　?、谧约憾x迭代次數(shù)。增加迭代次數(shù)可以使社區(qū)發(fā)現(xiàn)的結(jié)果趨于穩(wěn)定，但是會(huì)增加怪獸社區(qū)產(chǎn)生概率。減小迭代次數(shù)會(huì)讓小社區(qū)不被吞噬，但是會(huì)增加算法隨機(jī)性。所以該算法可以自定義迭代次數(shù)，使得在隨機(jī)性和怪獸社區(qū)之間找到平衡；
　?、鬯惴梢宰赃m應(yīng)的對(duì)怪獸社區(qū)進(jìn)行再次分割。用戶可以自己限定怪獸社區(qū)的最小節(jié)點(diǎn)數(shù)量，當(dāng)檢測(cè)到已經(jīng)

4、發(fā)現(xiàn)的社區(qū)數(shù)量大于怪獸社區(qū)節(jié)點(diǎn)最小數(shù)量時(shí)，算法就會(huì)對(duì)發(fā)現(xiàn)的怪獸社區(qū)進(jìn)行再次分割，直到所有社區(qū)的節(jié)點(diǎn)數(shù)量都小于怪獸社區(qū)節(jié)點(diǎn)數(shù)量最小值，從而杜絕怪獸社區(qū)的產(chǎn)生。
　　通過(guò)對(duì)不同的網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果進(jìn)行分析，表明了相對(duì)原始標(biāo)簽傳播算法、speaker-listener標(biāo)簽傳播算法以及衰減標(biāo)簽傳播算法，自適應(yīng)控制距離的標(biāo)簽傳播算法在不影響時(shí)間復(fù)雜性和社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量的前提下，得到的社區(qū)數(shù)量更加均勻，同時(shí)可以有效防止怪獸社區(qū)的產(chǎn)生。