社交網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題的研究.pdf

1、復(fù)雜網(wǎng)絡(luò)普遍具有社區(qū)結(jié)構(gòu)。在社區(qū)內(nèi)部節(jié)點(diǎn)連接緊密，而在社區(qū)之間節(jié)點(diǎn)連接稀疏。社交網(wǎng)絡(luò)中也存在著這種社區(qū)結(jié)構(gòu)，例如在社交網(wǎng)站上人們按照好友關(guān)系結(jié)合為朋友圈。對社交網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)是理解其網(wǎng)絡(luò)結(jié)構(gòu)，探索其網(wǎng)絡(luò)功能的重要方法。劃分社交網(wǎng)絡(luò)得到的社區(qū)結(jié)構(gòu)對研究社交網(wǎng)絡(luò)上的信息傳播，進(jìn)行好友或商品推薦等有著重要意義。
　　本文首先深入分析了社交網(wǎng)絡(luò)模型的結(jié)構(gòu)性質(zhì)。然后對邊的局部聚類系數(shù)和符號網(wǎng)絡(luò)中的結(jié)構(gòu)平衡理論做了進(jìn)一步擴(kuò)展。最后針對無符號

2、網(wǎng)絡(luò)和符號網(wǎng)絡(luò)這兩種社交網(wǎng)絡(luò)模型分別提出了更加高效和穩(wěn)定的社區(qū)發(fā)現(xiàn)算法。具體如下：
　　1）分析了無符號網(wǎng)絡(luò)中局部聚類系數(shù)和節(jié)點(diǎn)相似度計算的特點(diǎn)，提出了擴(kuò)展局部聚類系數(shù)作為無符號網(wǎng)絡(luò)中邊的結(jié)構(gòu)屬性。該屬性更能夠體現(xiàn)出局部網(wǎng)絡(luò)密度和網(wǎng)絡(luò)結(jié)構(gòu)的特點(diǎn)。將這種新的邊結(jié)構(gòu)測度與具有線性時間復(fù)雜度的標(biāo)簽傳播算法相結(jié)合，提出了結(jié)合擴(kuò)展局部聚類系數(shù)的標(biāo)簽傳播算法。在多種真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行的實(shí)驗表明：本算法能夠有效地在無符號社交網(wǎng)絡(luò)上進(jìn)行社

3、區(qū)發(fā)現(xiàn)并且在精確度和穩(wěn)定性上都得到了提高。
　　2）首先針對傳統(tǒng)標(biāo)簽傳播算法在網(wǎng)絡(luò)存在負(fù)邊時無法使用的問題，提出了一種新的符號網(wǎng)絡(luò)標(biāo)簽傳播算法。然后對符號網(wǎng)絡(luò)的結(jié)構(gòu)平衡理論進(jìn)行了深入分析，提出了能夠度量符號網(wǎng)絡(luò)中邊的結(jié)構(gòu)平衡程度和局部網(wǎng)絡(luò)密度的結(jié)構(gòu)平衡度。將結(jié)構(gòu)平衡度應(yīng)用在符號網(wǎng)絡(luò)上的標(biāo)簽傳播過程中，提出了結(jié)合結(jié)構(gòu)平衡度的符號網(wǎng)絡(luò)標(biāo)簽傳播算法。該算法促使標(biāo)簽在結(jié)構(gòu)平衡、正邊密度高的局部網(wǎng)絡(luò)內(nèi)傳播，阻礙其在負(fù)邊密度大、結(jié)構(gòu)不平衡的局