在線社交網(wǎng)絡(luò)中基于標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法的研究.pdf

1、隨著互聯(lián)網(wǎng)技術(shù)和Web2.0應(yīng)用的飛速發(fā)展，大量形態(tài)各異的在線社交網(wǎng)絡(luò)風(fēng)靡世界，成為人們分享和傳遞信息的重要平臺(tái)，也幫助人們?cè)诰W(wǎng)絡(luò)中維系著自己的社會(huì)關(guān)系。因此，研究社交網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)有著非常現(xiàn)實(shí)的意義，也成為近些年的研究熱點(diǎn)。
　　研究人員曾提出過很多社區(qū)發(fā)現(xiàn)算法，然而很多算法都有時(shí)間復(fù)雜度較高的問題?；跇?biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法具有接近線性韻時(shí)間復(fù)雜度，它對(duì)圖中每個(gè)頂點(diǎn)分配一個(gè)代表其所在社區(qū)的標(biāo)簽，按照隨機(jī)順序?qū)γ總€(gè)頂點(diǎn)進(jìn)行標(biāo)簽

2、更新。一個(gè)頂點(diǎn)若具有多個(gè)滿足條件的候選標(biāo)簽，則隨機(jī)選擇標(biāo)簽。然而該算法的結(jié)果包含很多小而碎的社區(qū)，且結(jié)果很不穩(wěn)定。因此我們提出了基于標(biāo)簽影響值的社區(qū)發(fā)現(xiàn)算法(LIB)。LIB算法選取一個(gè)種子集，為其中的頂點(diǎn)分配標(biāo)簽并按頂點(diǎn)度排序進(jìn)行傳播，在傳播過程中為每一種標(biāo)簽計(jì)算標(biāo)簽影響值來選擇標(biāo)簽。我們?cè)诓煌愋偷臄?shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明LIB算法在復(fù)雜度相近的情況下明顯提高了所發(fā)現(xiàn)社區(qū)的質(zhì)量，并有很好的穩(wěn)定性。
　　為了能更多的

3、考慮社交網(wǎng)絡(luò)中的動(dòng)態(tài)行為，并且更多的從社會(huì)學(xué)意義上提高社區(qū)發(fā)現(xiàn)的質(zhì)量，我們提出了基于標(biāo)簽影響向量的社區(qū)發(fā)現(xiàn)算法(LIVB)。LIVB算法將在線社交網(wǎng)絡(luò)中的文章、視頻等多種類型的實(shí)體作為圖中的頂點(diǎn)，共同參與標(biāo)簽傳播的過程。根據(jù)用戶行為的不同將圖中的邊分為靜態(tài)邊和動(dòng)態(tài)邊。傳播過程中為每一種標(biāo)簽計(jì)算標(biāo)簽影響向量來選擇標(biāo)簽。我們通過實(shí)驗(yàn)說明了這種類型的圖要比傳統(tǒng)的社交網(wǎng)絡(luò)圖的效果更好，LIVB算法所發(fā)現(xiàn)社區(qū)的主題性更強(qiáng)，質(zhì)量更好，并且保持了接近