基于標簽傳播及適合度的社團聚類算法研究.pdf

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

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

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

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