復雜網(wǎng)絡社團檢測算法及其應用研究.pdf

1、現(xiàn)實世界中大量復雜系統(tǒng)可以抽象為復雜網(wǎng)絡模型,社團結構是復雜網(wǎng)絡的關鍵結構特征,網(wǎng)絡的整體功能是網(wǎng)絡中各社團相互作用的結果。因此社團結構檢測是復雜網(wǎng)絡研究中的重要內容。
　　本文研究復雜網(wǎng)絡社團檢測算法及其在生物領域和社會領域的應用,主要包括以下幾點:
　　1.在很多真實網(wǎng)絡中,由于一個頂點需要行使不同的功能,該頂點可能同時屬于多個社團,這導致社團間存在一定程度的重疊,為了檢測重疊社團結構,對近鄰傳播算法(AP)進行改進,提

2、出一個重疊社團檢測算法OAP。AP算法檢測社團結構時,先識別出所有社團的中心點,再為每個頂點唯一指派一個中心點,擁有相同中心點的頂點集合就構成了一個社團。在中心點指派時,有時會出現(xiàn)頂點在多個中心點間難以選擇的情況,AP通過擾動網(wǎng)絡避免這種情況發(fā)生,而該現(xiàn)象可以作為識別重疊點、設計OAP算法的重要依據(jù)。OAP先用AP對網(wǎng)絡硬劃分,再利用AP的上述特點識別重疊點的候選集,最后將候選集里那些會使社團變稀疏的頂點作為噪聲過濾掉,即得到重疊社團結

3、構。實驗利用空手道網(wǎng)絡驗證了候選集選擇策略的合理性,利用蛋白質相互作用網(wǎng)絡驗證了算法能夠更準確的檢測社團結構,并且檢測到的社團更有意義。實驗結果說明OAP算法是一個有效的重疊社團檢測算法。
　　2.除了拓撲結構,網(wǎng)絡中的頂點還具有屬性信息,為了檢測拓撲結構稠密且屬性信息相似的社團,提出一個基于頂點特征的社團檢測算法。首先定義頂點間基于特征子空間的特征相似性,然后結合頂點特征相似性和拓撲相似性,計算網(wǎng)絡中邊的相似性,接著利用單鏈接分

4、層凝聚算法對邊聚類,最后提取邊上的公共特征作為社團特征。實驗利用Facebook網(wǎng)絡數(shù)據(jù)驗證了算法能夠快速準確的檢測出社團結構,并能很好的解釋社團含義。利用酵母 PPI數(shù)據(jù)說明算法能夠準確檢測到具有生物意義的社團,并給出該社團可能行使功能的時間。實驗結果說明算法具有普適性,能夠在頂點具有屬性信息的網(wǎng)絡中識別有意義的社團結構。
　　3.分析動態(tài)網(wǎng)絡不同時刻間社團結構的變化以研究網(wǎng)絡演化規(guī)律與特點是動態(tài)網(wǎng)絡研究的重點。由于動態(tài)網(wǎng)絡相鄰

5、采樣時刻網(wǎng)絡結構一般變化不大,為避免對相似網(wǎng)絡重復聚類,提出一個基于橋系數(shù)的靜態(tài)局部社團檢測算法和在此基礎上的增量社團檢測算法。首先利用靜態(tài)算法提取每個社團的最小橋系數(shù)生成樹,最小橋系數(shù)生成樹的導出子圖就是t?1時刻的社團結構,然后通過橋系數(shù)的變化判斷t時刻可能出現(xiàn)結構變化的社團,最后局部調整這些社團,以得到符合t時刻網(wǎng)絡拓撲的社團結構。實驗利用足球隊網(wǎng)絡數(shù)據(jù)驗證了靜態(tài)局部社團檢測算法的精確性,利用構造數(shù)據(jù)驗證了增量算法的精確性,利用D

6、BLP數(shù)據(jù)驗證了增量算法的高效性。實驗結果說明算法能夠利用前一時刻的社團結構和增量信息,快速準確的檢測當前時刻的社團結構。
　　4.蛋白質復合體預測對理解生物體結構與功能之間的關系具有極其重要的意義。研究發(fā)現(xiàn)蛋白質復合體由一個核和一些附屬蛋白質構成,對復合體的拓撲結構目前沒有明確的定義,本文從邊的角度刻畫復合體的核結構,提出一個基于邊的蛋白質復合體檢測算法。算法首先識別出所有的核邊,然后對核邊聚類得到候選核,接下來過濾候選核以保證

7、其中不存在重疊程度較高的核,最后檢測每個核的附屬蛋白質,得到蛋白質復合體。實驗利用DIP數(shù)據(jù)庫中的酵母PPI和文獻中的Gavin PPI數(shù)據(jù),驗證了算法的精確性。實驗結果說明算法能夠更準確的檢測蛋白質復合體,識別出位置一致性和語義相似性都更高的復合體。
　　5.作為溝通和分享信息的平臺,在線社交網(wǎng)絡已是人們生活中必不可少的一部分,為注冊用戶推薦朋友是社交網(wǎng)站必須提供的重要服務,為了解決這個問題,提出基于社交圈的朋友推薦算法。算法基