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

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

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

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

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