基于標(biāo)簽傳播算法的社區(qū)發(fā)現(xiàn)新算法.pdf

1、互聯(lián)網(wǎng)近年來(lái)的飛速發(fā)展，造就了一批以社交為主的網(wǎng)站，其中國(guó)外的Facebook， Twitter，Google+，國(guó)內(nèi)的QQ空間，豆瓣，人人等最為流行。這些社交網(wǎng)站每天都會(huì)有大量的用戶使用，并且產(chǎn)生大量的分享數(shù)據(jù)，建立新的朋友關(guān)系等。對(duì)于這些數(shù)據(jù)來(lái)說，具有很高的利用價(jià)值，比如網(wǎng)絡(luò)營(yíng)銷，輿情分析等。因此對(duì)這些數(shù)據(jù)的處理方式尤為重要，其中社區(qū)發(fā)現(xiàn)是研究熱點(diǎn)。本文主要是針對(duì)目前常用的社區(qū)發(fā)現(xiàn)算法進(jìn)行改進(jìn)。最常用的標(biāo)簽傳播算法 LPA的思想是在

2、初始情況下，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都被初始化為唯一的標(biāo)簽，在迭代更新每個(gè)節(jié)點(diǎn)的標(biāo)簽時(shí)，節(jié)點(diǎn)是根據(jù)其鄰居節(jié)點(diǎn)中標(biāo)簽個(gè)數(shù)最多的作為更新標(biāo)簽，如果標(biāo)簽個(gè)數(shù)最多的標(biāo)簽并不是唯一的，那么隨機(jī)從中選擇一個(gè)標(biāo)簽來(lái)更新當(dāng)前節(jié)點(diǎn)，最終達(dá)到收斂或者震蕩，該算法停止。由于該算法的思想和實(shí)現(xiàn)過程導(dǎo)致該算法有一些缺點(diǎn)，例如不穩(wěn)定性，發(fā)現(xiàn)的社區(qū)要么是巨型社區(qū)，要么就是無(wú)意義的小型社區(qū)，分布極其不均勻并且對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)比較敏感，二分網(wǎng)絡(luò)情況下會(huì)發(fā)生循環(huán)震蕩。
　　本文

3、針對(duì)上述LPA算法的一系列缺點(diǎn)，提出了LAAPA（label-attribute&attenuation progagation algorithm），基于標(biāo)簽屬性和衰減因素的社區(qū)發(fā)現(xiàn)算法。該算法引人了傳播衰減因子和節(jié)點(diǎn)屬性，其中傳播衰減因子顧名思義就是節(jié)點(diǎn)標(biāo)簽的傳播距離是有限的，并且隨著距離的增加節(jié)點(diǎn)標(biāo)簽的影響力逐漸降低，更新標(biāo)簽的權(quán)重也隨之減少；節(jié)點(diǎn)屬性是指在社交網(wǎng)絡(luò)中節(jié)點(diǎn)之間的關(guān)系并不僅僅是關(guān)注與被關(guān)注這種簡(jiǎn)單的傳統(tǒng)上的“邊”，為

4、了與實(shí)際情況更加吻合本文提出了節(jié)點(diǎn)屬性，具體是指將節(jié)點(diǎn)的其他屬性比如豆瓣網(wǎng)中用戶加入的“小組”作為節(jié)點(diǎn)的屬性，節(jié)點(diǎn)之間的相同屬性將會(huì)反映到節(jié)點(diǎn)之間的邊上，使用權(quán)值來(lái)表示。在算法迭代中，節(jié)點(diǎn)更新標(biāo)簽時(shí)，將考慮鄰居節(jié)點(diǎn)的標(biāo)簽傳播距離，節(jié)點(diǎn)之間邊的權(quán)值，節(jié)點(diǎn)的度等因素。本文通過兩組標(biāo)準(zhǔn)數(shù)據(jù)對(duì)提出的LAAPA算法和LPA算法進(jìn)行比較，在社區(qū)大小，模塊度等方面LAAPA算法發(fā)現(xiàn)的社區(qū)比LPA算法效果好。在使用Scrapy抓取的豆瓣網(wǎng)數(shù)據(jù)中，經(jīng)過清