在線社會(huì)網(wǎng)絡(luò)中基于屬性的重疊社區(qū)發(fā)現(xiàn)算法研究與應(yīng)用.pdf

1、研究表明，網(wǎng)絡(luò)已成為現(xiàn)實(shí)世界中許多系統(tǒng)的存在形式，而大多數(shù)現(xiàn)實(shí)網(wǎng)絡(luò)中都普遍具有一個(gè)共同特征，即社區(qū)結(jié)構(gòu)。針對(duì)在線社會(huì)網(wǎng)絡(luò)的眾多研究方向中，有一個(gè)非常有商業(yè)價(jià)值的研究領(lǐng)域即重疊社區(qū)發(fā)現(xiàn)。重疊社區(qū)不同于之前圖論中提出的網(wǎng)絡(luò)社區(qū)的概念，主要區(qū)分點(diǎn)是在重疊社區(qū)中，節(jié)點(diǎn)可以歸屬于不同社區(qū)。對(duì)于在線社會(huì)網(wǎng)絡(luò)，一個(gè)節(jié)點(diǎn)是一個(gè)真實(shí)的人物，這些節(jié)點(diǎn)理所應(yīng)當(dāng)?shù)木邆淞巳怂赜械亩嗝嫘?，即按照不同的?cè)面可以屬于不同的社區(qū)。因而重疊社區(qū)的概念更符合在線社會(huì)網(wǎng)絡(luò)中

2、社區(qū)的實(shí)際特征。
　　本文提出了兩種針對(duì)在線社會(huì)網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)算法，所研究的對(duì)象是如twitter、新浪微博、豆瓣網(wǎng)等具有關(guān)注關(guān)系的在線社會(huì)網(wǎng)絡(luò)。兩種算法分別基于社會(huì)屬性網(wǎng)絡(luò)的兩種屬性:一種是基于動(dòng)態(tài)屬性的動(dòng)態(tài)屬性群算法，一種是根據(jù)靜態(tài)屬性進(jìn)行社區(qū)發(fā)現(xiàn)的基于興趣的標(biāo)簽傳播算法。
　　動(dòng)態(tài)屬性群算法的大體思路是先根據(jù)關(guān)注關(guān)系將整張網(wǎng)絡(luò)圖劃分為兩部分，如受關(guān)注度前10％的節(jié)點(diǎn)為動(dòng)態(tài)屬性節(jié)點(diǎn)，其余為普通用戶節(jié)點(diǎn)。其后根據(jù)普通用

3、戶節(jié)點(diǎn)的關(guān)注關(guān)系對(duì)動(dòng)態(tài)屬性群進(jìn)行聚類。最后根據(jù)聚類結(jié)果確定普通用戶節(jié)點(diǎn)的重疊社區(qū)劃分。因?yàn)殛P(guān)注關(guān)系是可以由網(wǎng)絡(luò)中的節(jié)點(diǎn)動(dòng)態(tài)修改的，關(guān)注對(duì)象是動(dòng)態(tài)的，所以這個(gè)算法是基于動(dòng)態(tài)屬性的。
　　基于興趣的標(biāo)簽傳播算法建立在標(biāo)簽傳播算法的基礎(chǔ)上，主體上使用社區(qū)重疊傳播算法(COPRA)的思路，通過歸屬系數(shù)判斷標(biāo)簽是否被保留，從而能夠發(fā)現(xiàn)重疊社區(qū)。與之不同的是在標(biāo)簽傳播過程中不再使用“倒數(shù)系數(shù)”來隨機(jī)判斷節(jié)點(diǎn)是否保留標(biāo)簽，而是采用衰減因子與節(jié)點(diǎn)

4、特征算法（HANP）中對(duì)標(biāo)簽傳播能力的刻畫，保留每個(gè)節(jié)點(diǎn)在傳播過程中收到的有傳播能力的所有標(biāo)簽。標(biāo)簽傳播的對(duì)象是在線社會(huì)網(wǎng)絡(luò)中獨(dú)有的“個(gè)人標(biāo)簽”的概念，經(jīng)過類似動(dòng)態(tài)屬性聚類過程減少了傳播的標(biāo)簽總數(shù)，大大加強(qiáng)了標(biāo)簽傳播算法的語義性。
　　本文提出的兩種算法不同于傳統(tǒng)的圖論算法從節(jié)點(diǎn)或邊的角度出發(fā)，更多的是從社會(huì)學(xué)的三元閉包角度出發(fā)，因而更加符合在線社會(huì)網(wǎng)絡(luò)的形態(tài)特征，對(duì)于在線社會(huì)網(wǎng)絡(luò)中的重疊社區(qū)發(fā)現(xiàn)更加有效。
　　本文設(shè)計(jì)了一