基于節(jié)點相似性的加權(quán)復雜網(wǎng)絡BGLL社團檢測方法①

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

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

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

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

目前,已有的全局算法和局部算法均各有優(yōu)缺點.

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

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

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

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

1 BGLL加權(quán)網(wǎng)絡重疊社團檢測及其改進

1.1 改進的BGLL社團檢測算法

BGLL算法在稀疏網(wǎng)絡上具有時間復雜度線性的優(yōu)勢,算法結(jié)果穩(wěn)定,社團檢測結(jié)果較準確,計算簡單且易于實現(xiàn),使該算法具有較大的應用空間和較高的應用價值.

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

設(shè)節(jié)點i的度為d(i),權(quán)值為w(i),聚集系數(shù)為c(i),加權(quán)節(jié)點重要度為I(i)w,計算方法如下:

α在0到1之間,實驗發(fā)現(xiàn)當α為0.5時能較好的兼顧節(jié)點權(quán)重和網(wǎng)絡聚集程度,故α取值為0.5.

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

對于加權(quán)網(wǎng)絡,模塊密度采用通用模塊密度[14],設(shè)k為社團個數(shù),V為社團i內(nèi)節(jié)點個數(shù),diin為社團i內(nèi)節(jié)點連邊的權(quán)重和,diout為社團i內(nèi)點與社團i外節(jié)點的邊的權(quán)重和,D為模塊密度,計算方法如下:

參數(shù)λ在0～1之間,調(diào)節(jié)λ可以分析復雜網(wǎng)絡的拓撲結(jié)構(gòu)和層次結(jié)構(gòu): 若λ為0.5則表示D為模塊密度,若λ為0則表示D為比率割集,若λ為1則表示D為比率關(guān)聯(lián).本文使用模塊密度,因此采用λ為0.5.

1.2 改進的Jaccard相似度

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

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

設(shè)節(jié)點i為網(wǎng)絡中節(jié)點,節(jié)點j屬于社團C,節(jié)點i與社團C間的加權(quán)Jaccard相似度為Jw(i,C),計算方法如下:

1.3 重疊結(jié)構(gòu)判斷

用于判斷網(wǎng)絡中的節(jié)點與社團是否存在重疊結(jié)構(gòu),實現(xiàn)方式如下: 將改進的BGLL社團檢測算法運算得到的社團檢測結(jié)果進行網(wǎng)絡中各節(jié)點與各社團加權(quán)Jaccard相似度計算,根據(jù)計算結(jié)果的值判斷是否檢測到重疊結(jié)構(gòu).如果對以上運算的結(jié)果直接進行重疊結(jié)構(gòu)判斷,設(shè)γ是網(wǎng)絡內(nèi)各節(jié)點與各社團加權(quán)Jaccard相似度計算結(jié)果,節(jié)點i為網(wǎng)絡內(nèi)任意節(jié)點,Cj,Ck是改進的BGLL社團檢測算法檢測結(jié)果中的社團,γ的計算如下:

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

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

2 DBGLLJ加權(quán)重疊社團檢測算法

為了在加權(quán)復雜網(wǎng)絡中檢測出重疊社團,詳細的DBGLLJ算法設(shè)計如算法1.

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

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

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

3 實驗分析

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

3.1 評價指標

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

3.2 LFR基準網(wǎng)絡實驗

經(jīng)典的LFR基準網(wǎng)絡[11]參數(shù)意義見表1.

表1 參數(shù)意義

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

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

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

圖1 LFR基準網(wǎng)絡社團檢測效果對比

3.3 真實網(wǎng)絡檢測實驗

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

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

3.4 現(xiàn)實復雜機電系統(tǒng)因效性網(wǎng)絡應用實驗

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

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

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

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

4 總結(jié)

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

表2 真實網(wǎng)絡檢測結(jié)果Qov對比

表3 復雜機電系統(tǒng)網(wǎng)絡系數(shù)

表4 現(xiàn)實復雜機電系統(tǒng)網(wǎng)絡DBGLLJ算法結(jié)果

圖2 現(xiàn)實復雜機電系統(tǒng)重疊網(wǎng)絡檢測整體結(jié)果圖

表5 現(xiàn)實復雜機電系統(tǒng)社團10

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