基于標(biāo)簽傳播及適合度的社團(tuán)聚類算法研究.pdf

1、現(xiàn)實(shí)世界中的很多網(wǎng)絡(luò)系統(tǒng)都可以抽象成社會網(wǎng)絡(luò)，在這些網(wǎng)絡(luò)中，節(jié)點(diǎn)表示個體，節(jié)點(diǎn)之間的邊表示個體之間的相互聯(lián)系。隨著對社會網(wǎng)絡(luò)研究的不斷深入，人們發(fā)現(xiàn)網(wǎng)絡(luò)具有社團(tuán)結(jié)構(gòu)的特性，在社團(tuán)結(jié)構(gòu)內(nèi)部，節(jié)點(diǎn)之間的連接比較緊密，而社團(tuán)與社團(tuán)之間的節(jié)點(diǎn)連接較為稀疏。社團(tuán)結(jié)構(gòu)往往代表了網(wǎng)絡(luò)中具有某一相同屬性特征的節(jié)點(diǎn)集合，挖掘網(wǎng)絡(luò)中這種社團(tuán)結(jié)構(gòu)對研究社會網(wǎng)絡(luò)的演化過程、分析網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)以及了解網(wǎng)絡(luò)潛在的功能都具有非常重要的意義。
　　本文圍繞著如何

2、快速且有效地對網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)進(jìn)行聚類這一問題進(jìn)行了相關(guān)研究。本文首先分析總結(jié)了社團(tuán)聚類的相關(guān)背景與研究現(xiàn)狀，研究了有關(guān)社會網(wǎng)絡(luò)的重要理論，為后續(xù)研究奠定了理論基礎(chǔ)。對基于局部信息的標(biāo)簽傳播算法（LPA算法）進(jìn)行了深入研究與分析，發(fā)現(xiàn)LPA算法在算法迭代過程中會出現(xiàn)“標(biāo)簽?zāi)媪鳌爆F(xiàn)象，同時初始化標(biāo)簽數(shù)目過多，標(biāo)簽更新條件單一、不全面，標(biāo)簽更新策略具有隨機(jī)性等問題，針對這些問題給出了總體的解決方案。在具體實(shí)現(xiàn)這個解決方案的基礎(chǔ)上，本文提出了

3、一種帶有適合度的標(biāo)簽傳播算法，記為LPA-FA算法。
　　LPA-FA算法首先將網(wǎng)絡(luò)中所有的節(jié)點(diǎn)按照其度的大小進(jìn)行排序，組成了一個有序的節(jié)點(diǎn)序列，在每次算法迭代過程中，都按照這個節(jié)點(diǎn)序列依次進(jìn)行節(jié)點(diǎn)標(biāo)簽更新，避免了LPA算法由于采用隨機(jī)節(jié)點(diǎn)序列而造成的“標(biāo)簽?zāi)媪鳌爆F(xiàn)象，提高了算法效率。在節(jié)點(diǎn)標(biāo)簽初始化過程中，在LPA-FA算法中設(shè)計(jì)了一種簡單線性初始化方法，減少了網(wǎng)絡(luò)中初始標(biāo)簽的個數(shù)，從而降低算法的運(yùn)行時間。然后在節(jié)點(diǎn)標(biāo)簽傳播過程

4、中，當(dāng)節(jié)點(diǎn)的更新標(biāo)簽出現(xiàn)不唯一時，LPA-FA算法引入了鄰接子系統(tǒng)聚集系數(shù)、鄰接邊權(quán)重、節(jié)點(diǎn)屬性相似度三個參數(shù)，進(jìn)而通過Topsis方法得到三者的綜合評價值標(biāo)簽適合度，最終選擇使標(biāo)簽適合度最大的鄰接子系統(tǒng)內(nèi)的標(biāo)簽作為更新標(biāo)簽，不僅解決了LPA算法節(jié)點(diǎn)標(biāo)簽更新條件單一、不全面的缺陷，也克服了LPA算法的隨機(jī)性，從而降低算法的時間開銷，提高了聚類社團(tuán)的質(zhì)量。
　　最后，將LPA-FA算法與LPA算法分別在Zachary空手道俱樂部網(wǎng)絡(luò)