基于節點相似性的加權復雜網絡BGLL社團檢測方法①

賈鄭磊,谷 林,高智勇,謝軍太

1(西安工程大學 計算機科學學院,西安 710048)

2(西安交通大學 中國西部質量科學與技術研究院,西安 710049)

現實世界中許多系統都可以用復雜網絡表示,社團結構是復雜網絡的重要特征之一,研究社團結構能夠幫助了解網絡的內部結構及特性,評估和預測網絡的功能.目前研究者們提出的社團檢測算法大多面向無權網絡,主要分為全局算法[1-10]和局部算法[11-15],而對于加權網絡中社團結構檢測的研究還相對較少.全局算法能夠較均衡地利用各節點間信息,但是一般時間復雜度較高,只能實現局部收斂;局部算法一般具有較低的時間復雜度,但是檢測結果容易受到起始點及隨機傳播過程的影響.同時,在許多現實復雜網絡系統中,節點往往具有多個屬性,使得節點可能屬于多個社團,這種重疊現象使得能夠充分利用全局和局部信息的重疊社團檢測方法具有更大的實用價值.

目前,已有的全局算法和局部算法均各有優缺點.

基于全局信息的模塊度優化社團檢測算法最早是文獻[1,2]提出的基于邊介數的GN分裂算法以及衡量指標模塊度,但是算法的時間復雜度較高;文獻[4]提出貪婪最大化模塊度的FN凝聚算法,在一定程度上降低了算法的時間復雜度;文獻[6]提出了基于模塊度增益的層次性貪婪BGLL算法,該算法在稀疏網絡上的時間復雜度是線性的,適用于大型網絡,是目前最優的模塊度優化算法.但傳統方法無法直接實現重疊社團的準確檢測,易受節點順序影響,存在分辨率限制[10]以及缺乏重疊結構檢測手段.

基于局部信息重疊社團檢測經典算法是文獻[11]提出的LFM算法,但是該方法基于隨機種子節點,劃分結果質量取決于種子節點.文獻[12]提出基于說話者—聽話者動態交互模式的改進的標簽傳播算法(SLPA),該方法能夠同時發現重疊結點和重疊社團,但是算法結果并不穩定.

目前仍缺乏能夠兼顧重疊與層次、時間復雜度與計算準確度的穩定性高的方法.

本文針對加權復雜網絡中的重疊社團檢測問題,首先利用節點重要度重構網絡,然后運用加權BGLL算法,以模塊密度增益作為迭代終止條件,最后結合加權節點與社團相似度實現重疊社團檢測,并與傳統BGLL算法和目前性能較好的SLPA算法進行準確率分析對比,探討本文所提方法的優勢.

1 BGLL加權網絡重疊社團檢測及其改進

1.1 改進的BGLL社團檢測算法

BGLL算法在稀疏網絡上具有時間復雜度線性的優勢,算法結果穩定,社團檢測結果較準確,計算簡單且易于實現,使該算法具有較大的應用空間和較高的應用價值.

本文在BGLL算法的基礎上進行了改進,針對節點順序敏感問題以及分辨率限制提出了加權節點重要度計算方法和升序排序策略并增加模塊密度作為算法終止條件,在充分利用全局和局部信息的同時,提高了算法的運算準確度和尋優排序速度.

設節點i的度為d(i),權值為w(i),聚集系數為c(i),加權節點重要度為I(i)w,計算方法如下:

α在0到1之間,實驗發現當α為0.5時能較好的兼顧節點權重和網絡聚集程度,故α取值為0.5.

對于加權網絡,模塊度增益采用增強模塊度增益[6],設m為網絡中所有邊的權重和,ki為節點i上所有邊的權重和,ki,in為節點i到某社團中所有節點的邊的權重和,∑in為某社團內部節點間連邊的權重和,∑tot為某社團中節點與網絡中所有節點連邊的權重和,ΔQw為模塊度增益,計算方法如下:

對于加權網絡,模塊密度采用通用模塊密度[14],設k為社團個數,V為社團i內節點個數,diin為社團i內節點連邊的權重和,diout為社團i內點與社團i外節點的邊的權重和,D為模塊密度,計算方法如下:

參數λ在0～1之間,調節λ可以分析復雜網絡的拓撲結構和層次結構: 若λ為0.5則表示D為模塊密度,若λ為0則表示D為比率割集,若λ為1則表示D為比率關聯.本文使用模塊密度,因此采用λ為0.5.

1.2 改進的Jaccard相似度

為了充分利用全局和局部信息,采用局部相似性度量Jaccard系數來衡量節點間的相似度.針對重疊社團檢測問題,提出了加權節點間相似度計算方法以及加權節點與社團相似度計算方法.

節點間的加權相似度在無權Jaccard節點間相似度[15]的基礎上考慮了節點間相關權重,設節點i的鄰居集合為nbs(i),節點j的鄰居集合為nbs(j),wih,wjh為兩節點與兩節點公共鄰居節點h的邊權,節點i和節點j的無權Jaccard節點間相似度為J(i,j),節點i和節點j的加權Jaccard節點間相似度為Jw(i,j),計算方法如下:

設節點i為網絡中節點,節點j屬于社團C,節點i與社團C間的加權Jaccard相似度為Jw(i,C),計算方法如下:

1.3 重疊結構判斷

用于判斷網絡中的節點與社團是否存在重疊結構,實現方式如下: 將改進的BGLL社團檢測算法運算得到的社團檢測結果進行網絡中各節點與各社團加權Jaccard相似度計算,根據計算結果的值判斷是否檢測到重疊結構.如果對以上運算的結果直接進行重疊結構判斷,設γ是網絡內各節點與各社團加權Jaccard相似度計算結果,節點i為網絡內任意節點,Cj,Ck是改進的BGLL社團檢測算法檢測結果中的社團,γ的計算如下:

然后用γ和給定的閾值r比較,有兩種情況:

如果γ小于等于給定的閾值r,表示檢測到重疊點,就把當前節點保存到對應的社團中.如果γ的值大于r,則表示沒有檢測到重疊結構.實驗發現,當節點或連接關系較多時,為了在較大層次上檢測到重疊社團且在一定程度上避免過重疊,r取0.1結果較好,故采用r=0.1.

2 DBGLLJ加權重疊社團檢測算法

為了在加權復雜網絡中檢測出重疊社團,詳細的DBGLLJ算法設計如算法1.

算法1.DBGLLJ加權重疊社團檢測算法(1)社團初始化: 把每個節點單獨作為一個社團;(2)節點預處理: 根據節點重要度對節點排序;(3)第一階段:1)根據節點重要度序列遍歷各節點;2)遍歷當前節點的鄰居節點序列;3)計算各鄰居節點加入當前節點所在社團前后的模塊度增益,選取鄰居節點中模塊度增益最大值并記錄對應鄰居節點;4)若最大模塊度增益大于0,則進行社團合并,從原社團中刪除該鄰

居結點,進行步驟(3)的2);若最大模塊度增益不大于0,則從步驟(3)的1)遍歷下一節點;若節點序列遍歷完,則進入第二階段;(4)第二階段:1)計算上一次迭代社團檢測結果的模塊密度;2)把上次迭代檢測出的社團作為節點從步驟(1)到步驟(3)重新開始迭代;3)計算迭代后的模塊密度,如果迭代前后的模塊密度增益大于0,則繼續進行步驟(4);如果模塊密度增益不大于0,則結束迭代,執行步驟(5);(5)重疊結構檢測:1)根據改進的Jaccard相似度計算原始網絡節點間相似度;2)在檢測結果的基礎上,根據節點間加權Jaccard相似度計算各節點與迭代后各社團的加權Jaccard相似度;3)根據預設的重疊點檢測閾值得到重疊檢測結果;(6)算法結束.

上述算法既可以檢測非重疊社團,還可以判斷是否檢測重疊結構,如果判斷為檢測到重疊結構,就把當前加權重疊社團檢測結果保存并展示出來,如果僅僅檢測非重疊社團,則可簡化該算法,省略第(5)步.

3 實驗分析

實驗分別以LFR基準網絡、真實網絡為測試數據集驗證本文所提DBGLLJ方法的有效性,設置與傳統BGLL算法以及較好的SLPA算法的對比實驗;并在現實復雜機電系統因效性網絡進行了應用.

3.1 評價指標

采用改進的標準化互信息NMI[16]來衡量和比較基于LFR基準網絡的重疊社團算法的精度,NMI越大說明算法精度越高;采用擴展模塊度Qov[17]衡量和比較真實網絡中重疊社團算法的準確度,Qov越大說明算法準確度越高,實驗發現p為30時指標使用效果較好,反應靈敏且計算效率較好,在此p取30.

3.2 LFR基準網絡實驗

經典的LFR基準網絡[11]參數意義見表1.

表1 參數意義

LFR網絡參數設置如下: 網絡規模N為1000;平均節點度k為20,最大節點度maxk為50;節點度和社團規模冪律分布參數分別為t1=2,t2=1.設置兩組不同的社團規模參數以生成兩種網絡: 較小規模網絡的minc=10,maxc=50;較大規模網絡的minc=20,maxc=100.混合參數u從0變化到0.7,間隔為0.1,測試不同混合程度下算法的社團檢測效果.

對于重疊網絡,設置om=5,節點數為1000的網絡中設置重疊節點數on從0到500變化,間隔為50,測試不同重疊程度下的社團檢測效果.

當進行社團檢測時,自動把當前社團檢測結果保存到文件中,圖1是分別在較小規模非重疊網絡、較大規模非重疊網絡以及較小規模重疊網絡上的對比算法的評估指標NMI的結果,從圖1可以看出,對于非重疊社團檢測而言,所提的DBGLLJ方法克服了傳統BGLL算法傾向發現較大規模社團的弊端,且在混合度小于等于0.6時具有最高的檢測準確度;而對于重疊社團檢測而言,所提算法的準確度也均優于其他兩個對比算法.

圖1 LFR基準網絡社團檢測效果對比

3.3 真實網絡檢測實驗

采用了美國空手道網絡Zachary[1]、海豚社交關系網絡Dolphins[18]、美國大學生足球比賽網絡Football[1]以及加權Zachary網絡[19].各網絡的節點規模n、邊數目m、度平均k、原社團個數v、對比算法檢測后對應社團個數v’以及評估指標Qov結果如表2.

表2說明在真實網絡中,所提的DBGLLJ算法均具有較高的Qov,且社團檢測結果在社團規模較小時具有更高的準確性.

3.4 現實復雜機電系統因效性網絡應用實驗

為真實準確可靠評估復雜機電系統服役質量狀態,研究復雜機電系統內部結構,有必要對系統內各變量因效性網絡進行社團結構檢測.網絡的節點表示現實系統各物理部件的關鍵指標,網絡的邊表示指標間的關聯強度.網絡的初步構建結果為自環全連接因效性網絡,但在現實世界中,復雜網絡多為稀疏網絡,即＜＜N-1,也常有的特點,網絡的關聯強度Wr、度平均k以及聚集系數C如表3,由表知Wr=0.5時網絡的聚集效果較好,因此去掉了網絡的自環并截取了Wr>0.5的關聯強度邊進行社團檢測.

最終的機電系統網絡包括157個節點和782條邊.將DBGLLJ算法應用于實際的復雜機電系統網絡,模塊度Q[2]、擴展模塊度Qov、社團檢測個數v以及重疊點個數o具體結果見表4.

從表4可知,該檢測結果模塊度較高(在0.3-0.7之間較好),重疊模塊度為0.927,重疊比例為7.9%,在此范圍內該算法重疊檢測效果較好,結果可信.檢測結果展示如圖2.

以圖2所示的較大社團10為例,將社團內各節點及其對應變量(表5)與實際復雜機電系統對比分析,發現該算法的檢測結果較符合系統內部結構關系,與實際情況下的系統的強弱社團情況接近,檢測結果較好,且重疊點具有較高的參考價值,能夠為進一步進行網絡評估和預測提供較準確的數據支持.

4 總結

目前,對于加權復雜網絡重疊社團檢測的算法還較少,且檢測效果和算法穩定性欠佳,如何充分利用全局和局部信息進行準確的重疊社團檢測具有重要意義.傳統的BGLL算法具有稀疏網絡時間復雜度線性、較大規模非重疊社團檢測準確度較高的優勢,但是對節點順序敏感、存在分辨率限制、缺乏重疊檢測手段,無法實現加權復雜網絡的重疊社團的準確檢測.

表2 真實網絡檢測結果Qov對比

表3 復雜機電系統網絡系數

表4 現實復雜機電系統網絡DBGLLJ算法結果

圖2 現實復雜機電系統重疊網絡檢測整體結果圖

表5 現實復雜機電系統社團10

為了實現加權復雜網絡重疊社團的準確檢測,本文提出的DBGLLJ算法利用了傳統BGLL算法未能充分利用的局部信息和全局信息,針對節點順序敏感問題提出加權節點重要度計算方法和升序排列策略,提高了尋優排序效率和檢測準確性;針對分辨率限制問題增加模塊密度作為迭代終止條件,改善了分辨率問題;針對重疊社團檢測提出運用改進的Jaccard相似度衡量原始網絡各節點與改進的BGLL算法社團檢測結果中各社團的相似性,并根據閾值檢測得到了重疊結構.實驗表明,所提的DBGLLJ算法的社團檢測精度得到提高,能夠檢測出重疊結構,且重疊社團檢測結果較優.將該算法應用于實際復雜機電系統進行分析,結果較滿意.