基于節點重要性和模塊度優化的社團劃分算法

張夢園,李玲娟

(南京郵電大學 計算機學院,江蘇 南京 210023)

0 引 言

對復雜網絡的深入研究發現,現實世界中許多系統都能抽象為網絡,如人與人之間的社交網絡、自然界的食物鏈網絡、蛋白質相互作用網絡等。這些網絡由具有一定組織性和極大隨機性的節點構成[1]。根據網絡節點之間的連邊是否存在權值,復雜網絡可以分為無權網絡和加權網絡,加權網絡相比無權網絡能夠反映更加豐富的信息,同時賦予復雜網絡更加明確的物理意義。

社團是復雜網絡的一個重要特征,社團內各個節點間連接緊密,而社團之間只有一些稀疏的連接[2]。發現復雜網絡中的社團結構能為進一步理解網絡所代表的真實世界系統的結構和功能提供捷徑。經典的社團劃分算法有基于模塊度優化的、基于標簽傳播的、基于局部擴展的、基于深度學習的等等[3-5]。針對加權網絡的社團劃分算法還相對較少,通常考慮引入邊的權值來對已有的經典的無權網絡劃分算法進行改進。典型的基于模塊度優化的加權復雜網絡的社團劃分算法有WGN[6]、WFN[7-8]、CNM[9]、BGLL等。

其中的BGLL[10]算法分為兩個階段,第一階段不斷將節點移入(即并入)使模塊度增益最大的社團,直至節點的移動不會再導致模塊度增加;第二階段將得到的社團作為新的節點對網絡進行重構,在重構的網絡上重復第一階段。BGLL算法在第二階段對網絡重構,極大地縮小了網絡規模,算法的迭代會越來越快,因此具有很好的時間效率,但由于第一階段迭代遍歷節點是無序的,沒有考慮節點自身在網絡中的地位,因此可能會使最終劃分結果的準確度不佳,仍有改進的空間。

該文考慮在無向加權網絡的社團劃分算法BGLL中引入節點重要性來調整其遍歷次序,以提高算法劃分結果的準確度。首先,設計了一種基于節點自身信息及其鄰居節點信息的加權網絡節點重要性計算方法WNI (weighted network node importance);然后,融合WNI和BGLL算法,設計了一種基于節點重要性和模塊度優化的加權網絡社團劃分算法(weighted network community division algorithm based on node importance and modularity optimization),命名為IMWCD。IMWCD算法將BGLL算法每輪合并后重構的網絡中的所有節點按照重要性升序排序,并作為下一輪遍歷的順序,以此為基礎實現加權網絡的社團劃分。

1 相關知識

1.1 網絡的圖表示

一個真實的加權網絡可以抽象表示為圖G=(V,E,W)的形式,其中V表示節點集,E表示邊集,W表示邊的權值,節點數n=|V|,邊數m=|E|,E中每一條邊都有V中的一對點與之對應,wij表示任意有邊相連的節點i和節點j之間的權值。對于無向網絡而言,任意點對(i,j)和(j,i)表示同一條邊,對應邊的權值wij=wji;對于有向網絡,節點之間的連邊具有方向性,如(i,j)唯一表示由節點i指向節點j的邊。與網絡中某個節點v直接相連的邊的數目稱為該節點的度dv。

1.2 節點重要性

有研究表明,網絡中重要性較大的節點相比其他節點更能影響網絡的結構和功能[11],重要性越大的節點越傾向于成為社團的中心。因此,節點重要性度量方法對于發現網絡的社團結構具有重要的意義。評價網絡中節點重要性的方法有很多,如介數中心性、度中心性、PageRank等。基于網絡全局屬性的介數中心性評價方法認為:經過某個節點的最短路徑數量越多,則該節點越重要[12],這種評價方法需要計算所有節點對之間的距離,時間復雜度過高。度中心性是最簡單的節點重要性評價指標,直接反映與當前節點相連的鄰居數量(即節點的度),節點的度越大,與之直接相連的鄰居節點越多,該節點越重要[13];這種評價方法具有計算復雜度低的優點,但只考慮了待評估節點的局部信息,沒有考慮鄰居節點的信息或節點在網絡中所處環境等因素,可能導致計算結果誤差較大。PageRank[14]是谷歌搜索引擎的核心算法,考慮的是待評估頁面的鄰居頁面信息對待評估頁面重要性的影響,認為如果一個頁面被大量其他頁面所指向,則此頁面是重要的。

1.3 BGLL算法

BGLL算法是一種層次性貪婪算法,基于模塊度優化的思想,自底向上地不斷合并網絡中的社團,取模塊度最大時的劃分狀態作為最終的劃分結果。BGLL算法首先將網絡中每個節點初始化為一個社團,社團編號為節點編號。之后的工作分為兩個階段。

第一階段:對于每個節點,考察其所有鄰居節點,嘗試將此節點移入其鄰居節點所在社團,并計算移入后的模塊度增益,如果計算得出的所有增益為負,則節點仍處于原始社團,否則選擇將節點移入模塊度增益最大的社團內。遍歷網絡中所有節點,直到沒有節點移動,即移動任意節點都不會再導致模塊度的增加,此時第一階段結束。其中,模塊度增益定義如下:

(1)

其中,∑in表示社團內部所有邊的權值之和,ki,in表示節點i與所在社團內的節點的連邊的權值之和,ki為節點i在網絡中的所有連邊的權值之和,∑tot表示節點i所在社團內的各個節點與網絡中所有節點連邊的權值之和,m為網絡中所有邊的權值之和。

第二階段:將網絡圖進行重構,規則如下:將第一階段劃分出的社團作為新的節點,社團編號作為新的節點編號。新的節點之間連邊的權值為兩個原社團之間連邊的權值之和,處在同一個社團內的節點使得新形成的節點有指向自己的自環邊,且權值為社團內所有連邊的權值之和。將第二階段重構的網絡圖作為第一階段的輸入重新進行迭代,直至網絡不再改變即模塊度最大時算法停止。

2 加權網絡節點重要性計算方法WNI設計

如前文所述,節點重要性能反映節點在網絡中的地位,重要性越大的節點越有可能成為社團的中心。合理使用節點重要性可以使社團劃分算法的劃分過程更具有方向性和目的性,從而獲得更準確的劃分結果。

該文借鑒度中心性和PageRank的評價思想,對加權網絡中的節點重要性做出如下的量化定義:

Ip=Ip'+IN

(2)

其中,Ip表示節點p的重要性,Ip'表示根據節點p自身權值信息計算得到的重要性,IN表示根據節點p的鄰居節點信息計算得到的重要性。

Ip'的定義如下:

(3)

(4)

其中,wmin表示網絡中邊的最小權值,wmax表示網絡中邊的最大權值。歸一化可以防止網絡規模過大時,直接計算邊的權值之和可能導致的數據溢出問題。

IN的定義如下:

(5)

其中,wjp表示節點j和節點p之間的權值,‖N(j)‖表示節點j的鄰居節點數目,wk表示節點j的鄰邊中第k條邊的權值。

以圖1所示的簡單加權網絡為例,其中節點v1擁有最多的連邊且與之相連的邊的權值在整個網絡中占比最大,該節點應該是網絡中最重要的節點。對于節點v2和v3,除了考察其自身的Iv',它們的共同鄰居v1對節點v3的重要性貢獻較大,則v3應比v2擁有更高的重要性值。

圖1 簡單加權網絡

可見,節點v1的重要性Iv1最大,計算結果與實際相符,說明該文設計的加權網絡的節點重要性計算方法WNI是合理有效的。

3 IMWCD算法設計與分析

如前文所述,BGLL算法第一階段節點的遍歷次序隨機,沒有考慮節點自身屬性信息及其所處環境信息,從而可能使最終的社團劃分結果的準確度不夠高。為了解決這個問題,該文設計了基于節點重要性和模塊度優化的加權網絡社團劃分算法IMWCD。

3.1 設計思路

IMWCD采用WNI方法計算節點重要性,將BGLL算法每次迭代中第一階段的節點遍歷順序由隨機遍歷調整為按節點重要性的升序遍歷,以便綜合利用全局和局部信息來提升算法的準確度。

3.2 IMWCD算法總體流程

算法總體流程可描述如下:

輸入:網絡圖G=(V,E,W);

輸出:加權網絡社團。

算法步驟:

Step1:初始化網絡中每個節點i∈V為一個社團,社團編號為節點編號;

Step2:根據式(2)至式(5)計算每個節點的重要性,并將所有節點按照重要性升序排列成節點序列list;

//迭代更新階段:

Step3:考察list中的首個節點;

Step4:遍歷當前節點的鄰居節點,計算當前節點移入其鄰居節點所在社團后的模塊度增益,記錄模塊度增益的最大值和對應的社團編號;

Step5:若最大模塊度增益大于零,將當前節點移入模塊度增益最大的社團;否則當前節點仍留在原始社團。繼續考察list中的下一個節點;

Step6:重復Step4、Step5,直至當前網絡中沒有節點需要移動;

Step7:計算Step6結束后整個網絡的模塊度,并與上一輪的網絡模塊度對比,如果網絡模塊度未增大,則當前的劃分結果為最終劃分結果,算法終止;否則,執行Step8;

//網絡重構階段:

Step8:將Step6中檢測出的每個社團分別作為一個節點,對網絡進行重構,將社團內的所有邊的權值之和作為新節點指向自身的自環邊的權值,新節點之間的權值為兩個原社團之間連邊的權值之和。將重構網絡作為輸入,重復Step2至Step7進行新一輪迭代。

IMWCD算法的具體流程如圖2所示。

圖2 IMWCD算法的具體流程

3.3 IMWCD算法分析

(1)實例分析。

在加權網絡圖中,權值代表了不同節點間聯系的緊密程度,而根據社團結構的定義,社團內部節點間聯系緊密,社團之間聯系稀疏。以圖3所示的簡單加權網絡為例來模擬IMWCD算法對加權網絡社團結構的劃分過程,檢驗其社團劃分效果。

圖3 加權網絡

用公式(2)至公式(5)計算每個節點的重要性,得到I1=2.266,I2=3.312,I3=1.753,I4=3.373,I5=1.942,I6=2.306,I7=2.066,按照節點重要性升序排列得到節點序列L={3,5,7,1,6,2,4}。

將網絡中的7個節點初始化為7個單獨的社團,編號與節點序號對應,分別為C1至C7。

迭代更新階段:首先考察節點序列L中的節點3(稱為目標節點),其鄰居節點所在社團集合為{1,2,4},根據公式(1)分別計算將節點3移入其鄰居節點所在社團Ci前后的模塊度增益ΔQi,分別為:ΔQ1=0.020 2,ΔQ2=0.061 8,ΔQ4=0.025 5,則選擇將節點3移入社團C2。同理,依次遍歷剩下的節點,以模塊度增益最大且為正值為原則,將節點移入相應社團,具體情況如表1所示。

表1 第一次遍歷的情況

由表1可知,第一次遍歷產生了三個社團,分別為C2(3),C4(1,2,4),C6(5,6,7)。因為有節點移動,所以再次從節點序列L的節點3開始新的遍歷,其當前所屬社團為C2,鄰居社團只有C4,將其移入C4的模塊度增益ΔQ4=0.107 4,因為ΔQ4>0,所以將其移入社團C4;繼續依次遍歷L中其余節點,計算得出這些節點的移動不會使模塊度增加(具體計算過程不再贅述),因此在本輪遍歷過程中節點3移入C4,C2消失,C6不變。即結果有2個社團,分別是C4(1,2,3,4),C6(5,6,7)。

因為有節點移動,所以要繼續從節點序列L的節點3開始新的遍歷,再次執行迭代更新,計算得出所有節點變動后的模塊度增益均小于零(具體計算過程不再贅述),即所有節點不需再移動,迭代更新階段結束,劃分出的社團結構如圖4所示。此時的網絡模塊度Q=0.428 2。

圖4 迭代更新結果

網絡重構階段:將迭代更新檢測出的社團作為節點,對網絡進行重構,重構的網絡如圖5所示。為了便于理解,新網絡的節點號用對應的社團號表示,兩個節點分別是C4和C6。

圖5 網絡重構結果

對重構后的網絡,用公式(2)至公式(5)計算每個節點的重要性得到IC4=2.026,IC6=1.460,升序排列的節點序列為L={C6,C4},重復迭代更新階段,此時兩個節點互為鄰居,C6移動到C4所在社團后的模塊度增益是ΔQC6=-0.428 3,C4移動到C6所在社團后的模塊度增益是ΔQC4=-0.428 3,都小于零,即都不需再移動,迭代更新結束,此時網絡模塊度為Q'=0.428 2,與上一輪迭代更新結束時的網絡模塊度Q相同,算法終止。最終劃分出的兩個社團編號分別為C4和C6。不難看出節點4和節點6在最初的節點重要性升序序列中確實處于高位,因此最終劃分的社團以節點4和6為中心,符合實際情況,驗證了WNI和IMWCD的有效性。

(2)時間復雜度分析。

在節點重要性計算過程中,根據節點自身權值信息計算重要性的時間復雜度為O(dn);d為網絡的平均度值,n為網絡中的節點數;基于鄰居節點信息計算重要性的時間復雜度為O(dn),按節點重要性升序排序節點的時間復雜度為O(n),因此對于節點重要性計算以及節點重要性排序的算法復雜度為O(dn+dn+n),即O((2d+1)n);傳統BGLL算法考察每個節點的鄰居節點,時間復雜度為O(dn),計算節點移動的模塊度變化的時間復雜度為O(n),移動節點的復雜度為O(n),網絡重構階段的時間復雜度為O(m),m為網絡中的邊數。因此BGLL算法的時間復雜度為O(dn+n+n+m),即O((d+2)n+m)。實際大規模網絡圖為稀疏圖,因此BGLL的時間復雜度近似O((d+2)n)。綜上,IMWCD算法的總復雜度為O((2d+1)n+(d+2)n+m),近似為O(3(d+1)n),算法總的時間復雜度仍然是接近線性的。

4 性能測試實驗及結果分析

該文分別在LFR人工基準網絡數據集和三個真實加權網絡數據集上對所設計的IMWCD算法的性能進行測試,并與BGLL算法和CNM算法做對比。其中,CNM算法首先將有N個節點的網絡初始化為n個社團,然后計算社團兩兩合并前后的模塊度增益,用堆結構來構造模塊度增量矩陣,選擇模塊度增益最大的社團進行合并,并更新模塊度增量矩陣,直至網絡中所有的節點都歸到一個社團。該算法針對稀疏網絡的時間復雜度為O(mlogn),其中m為邊數,n為節點數。

(1)實驗數據集。

(a)LFR人工基準網絡數據集。

實驗使用的LFR人工基準網絡數據集參數見表2。

表2 LFR基準網絡數據集參數

表中,N表示網絡中的節點數量;k表示節點的平均度;maxk表示節點的最大度值;maxc表示最大社團規模;minc表示最小社團規模;u表示混合系數,u越大,社團結構越不明顯。為了能夠對加權社團劃分算法做驗證,在數據集生成過程中,對于同一個社團內的連邊隨機生成[0.5,1]的權值,不同社團之間的邊隨機生成(0,0.5)的權值。

(b)真實網絡數據集。

實驗使用的三個較大規模真實網絡數據集分別是1995至1999年間高能物理研究領域(High-energy theory)和天體物理研究領域(Astrophysics)的科學家合作網絡,以及1995至2005年間凝聚態(Condensedmatter)研究領域的科學家合作網絡。以下分別簡稱H-th、A-ph、C-mat。邊的權值表示科學家們的合作次數。數據集的統計特征如表3所示。

表3 數據集統計情況

(2)評價指標。

用標準化互信息NMI[15]來衡量算法對LFR人工基準網絡的社團劃分準確度,NMI值越大,表明算法劃分精度越高;用模塊度Q來衡量算法對真實加權網絡的社團劃分質量,Q值越大,表明社團劃分的模塊化越強,劃分效果越好。

(3)結果分析。

(a)基于LFR人工基準網絡數據集的實驗結果。

使用三種算法分別對網絡N1和N2進行劃分,NMI的計算結果如表4所示。

表4 三種算法的NMI值

從表4可以看出,相同混合系數下,隨著節點數增多,各算法的NMI值略有下降。相同節點數的情況下,隨著混合系數的增加,網絡的社團結構越來越模糊,三個算法的表現也逐漸變差,但所設計的IMWCD算法的NMI值始終高于其他兩個算法,社團劃分的準確性優于其他對比算法。

(b)基于真實加權網絡數據集的實驗。

表5給出了三種加權網絡社團劃分算法在真實網絡數據集H-th、A-ph、C-mat上分別運行十次得到的平均模塊度Q值。

表5 真實加權網絡數據集社團劃分結果

從表5可以看出,IMWCD算法在三個較大規模的真實加權網絡數據集上的模塊度Q值都大于其他兩個算法,驗證了IMWCD算法在劃分準確度方面的優勢。

5 結束語

考慮到節點重要性對社團劃分過程具有更明確的指示作用,以及BGLL算法迭代更新過程中的節點遍歷順序會影響算法劃分結果的準確度,設計了一種基于節點重要性和模塊度優化的加權網絡社團劃分算法。綜合節點自身權值信息和其鄰居節點信息計算節點的重要性,以節點重要性的升序為BGLL算法的節點遍歷順序。理論分析和在人工網絡及真實加權網絡數據集上的實驗結果證明了IMWCD算法在保持線性時間復雜度的同時,克服了BGLL算法節點順序敏感問題,劃分結果的準確度有所提升,能夠對加權復雜網絡進行有效的社團劃分。