面向復雜有權網絡的社區發現方法研究

譚紅葉,吳永科,張 虎，劉全明,李 茹,2

(1. 山西大學 計算機與信息技術學院，山西 太原 030006；2. 山西大學 計算智能與中文信息處理教育部重點實驗室, 山西 太原 030006)

0 引言

隨著以互聯網為代表的網絡技術的快速發展，人類社會已邁入了復雜網絡時代。當前，人們生活在一個充滿各種類型網絡的復雜網絡世界。例如，社會網絡、電力與交通網絡、經濟與金融網絡等，在這些網絡中充斥著各種不同的關系和結構。隨著研究人員對網絡性質研究的不斷深入，人們發現許多實際網絡都有明顯的社區結構[1]，每個社區內部的節點之間的連接相對較為緊密，各個社區之間的連接相對比較稀疏。基于這些特征，人們對不同的社會網絡探索了很多實用的社區發現算法。典型的算法主要包括: (1)基于網絡拓撲結構的算法，主要有Pothen 等人[2]在20世紀90年代提出的基于譜分析方法的社區結構探測算法和Girvan 等人[3]提出的GN層次聚類算法。(2)基于網絡動力學的算法，主要包括Reichardt 和 Bornholdt[4-5]將物理學中Potts模型運用到社區發現中的超順磁聚類算法，Wu等人[6]將網絡類比成電路的電流算法。(3)基于模塊度優化的算法主要包括貪婪算法[7]和極值優化算法[8-9]等。(4)基于聚類的社區發現算法是尋找社會網絡中社團結構的一類傳統方法。它基于各個節點之間連接的相似性或者強度，把網絡自然地劃分為各個子群，根據向網絡中添加邊或者是從網絡中移除邊，該類算法可以分為兩類: 凝聚方法和分裂方法[10-12]。

顯然，這些典型的社區發現方法主要針對無權網絡，在這些網絡中節點之間的邊只有存在或不存在兩種情況，兩節點之間存在邊則連接強度為1，不存在則為0。但在很多實際網絡中，節點之間的權值不同，相互的耦合性不同，這些差異對分析復雜網絡的社區結構起著至關重要的作用。如科研合作網絡中，各個研究者之間的合作論文數量是不同的，合作論文數量多的研究者的緊密性通常更強；復雜交通網絡中，一個周期內不同城市間的航班班次和火車車次也相差巨大，來往次數較多的城市更容易形成一體化的經濟圈。顯然，復雜網絡中節點之間的連接強度會在很大程度上影響網絡的社區結構，因此利用權重來刻畫連接強度的差異性，并將其應用到社區發現研究中具有重要的意義[13-15]。

目前，針對有權網絡的社區發現研究已經成為一個重要的研究方向。相關研究主要有: Newman M E J[16]提出了WGN算法，是對GN算法的改進，將邊介數用權重的邊替換；王坤等人[17]提出了基于相似度的加權復雜網絡社區發現；韓華等人[18]基于現有的劃分算法提出改進的CNM算法對加權網絡進行劃分，該方法延續應用了社團結構分級聚類，對Newman貪婪算法[19]進行了改進。

本文結合節點的直接連邊權重和基于共同鄰節點的連邊權重提出了一種改進的節點相關度度量準則?；谶@種改進的節點相關度度量準則和團體之間的聚集方法構建了面向有權網絡的社區發現模型，分別在有權值的科學家合作網絡、全國列車運行網絡數據集上進行了社區發現實驗?；诹熊囘\行網絡數據集的實驗結果顯示出我國不同城市間的列車分布情況，發現了連接最緊密的城市群、包含較少節點的社區和孤立的城市節點等。

1 加權網絡節點相關度度量準則

1.1 節點相關度度量準則

在無權復雜網絡中，經典三元閉包原則指出，如果兩人A和B擁有一個共同的朋友C，那么這兩個人今后也很有可能成為朋友，從而使得三個節點構成一個閉包三角形ABC。對于一般的網絡，可以把這一原則推廣如下: 兩個節點的共同鄰居數量越多，這兩個節點越相似。本文將該原則應用到無向有權網絡中，同時在此基礎上將連邊權值引入到兩個節點間的相關度計算模型，節點相關度準則既考慮了兩個節點的共同鄰節點，同時又考慮了基于共同鄰節點的連邊權重。

對于復雜網絡，兩個節點間的連接強度除了與基于共同鄰節點形成的連邊相關外，還與直接相連的邊有關，因此計算兩個節點的相關度需要同時考慮基于共同鄰節點的連邊權重和直接連邊權重。本文通過設置參數α，β來調節直接連邊權重和基于共同鄰接點的連邊權重的關系，節點vi和vj之間的權重可以通過以下式(1)來表示:

(1)

其中，σij表示節點vi和vj本身的直接連邊權重，在復雜有權網絡中都會直接列出；σh表示節點vi和vj基于共同鄰節點的連邊權重，需要針對不同類型的復雜網絡構造對應的計算模型，針對該問題本文面向復雜有權網絡定義了基于共同鄰節點的連邊權重；n表示節點vi和vj的共同鄰節點數；α和β分別為直接連邊權重和基于共同鄰接點的連邊權重的調節參數，需通過實驗訓練，要求α+β=1。

1.2 基于共同鄰節點的連邊權重

假設{v1,v2,…,vn}表示節點vi和vj的共同鄰節點，{θi1,θi2,…,θin}表示節點vi與共同鄰節點的連邊權重，{θj1,θj2,…,θjn}表示節點vj與共同鄰節點的連邊權重。通過圖1可以看到節點vi和vj?？梢曰谒鼈兊墓侧徆濣c產生進一步的聯系。那么，對于有權網絡該如何通過共同鄰節點計算節點vi和vj的連接強度?；诰W絡流中的最大流理論，每一條路徑最大流的流值等于該路徑上最小容量的那條邊所能承受的流量。圖2中節點vi和vj通過公共鄰節點v相連，可以看到節點vi到節點v的容量為10，節點v到節點vj的容量為2。那么，按照最大流理論可以得到節點vi和vj間的最大流為2。

圖1 兩個節點的公共鄰節點

圖2 兩個節點間的最大流

因此，對于基于公共鄰節點v的連邊權值計算問題，依據最大流理論可以選取兩條邊的最小權值作為通過該節點v的連邊的權重。節點vi和vj的第h個公共鄰節點的連邊權值計算如式(2)所示。

σh=min(θih,θjh)

(2)

其中，θih和θjh分別表示節點vi和vj的第h個共同鄰節點的連邊權值, 且0≤h≤n。

1.3 基于兩種權值的統一表示框架

復雜網絡中的加權方式通常有兩種: 相異權和相似權。相異權是指權值越大，節點間的相關度越小，關系越疏遠；相似權是指權值越大，節點間的相關度越大，關系越緊密。本文研究的復雜有權網絡包括科學合作網絡和列車運行網絡，兩種復雜網絡只考慮無向情況。其中科學合作網絡的邊權賦予采用相似權的方式，列車運行網絡的邊權賦予采用相異權和相似權的組合方式。由于相異權考慮了節點間的距離，相似權考慮了節點間的關系緊密度，因此在列車運行網絡中通過這兩種權值的組合可以更準確地反應節點劃分的實際情況。本文將這兩種權值表示到統一的節點權重度量框架，具體表現形式如式(3)所示。

(3)

其中，σij和ζij分別表示節點vi和vj的相異權和相似權；x，y表示相異權和相似權的權重調節參數，且x+y=1。同時，式(3)分別對相異權的倒數和相似權做了標準化處理，使不同量綱的兩個變量都介于0到1之間，一定程度上保證了兩個參數的可調節性。式(3)可進一步寫成式(4):

σ(vi,vj)=x*min(σij)/σij+y*ζij/max(ζij)

(4)

在本文的實驗中，針對科學合作網絡數據集的實驗令相異權的調節參數x=0，相似權的調節參數y=1。對列車運行網絡數據集的實驗通過不斷調整x和y的取值分析兩個權對結果的影響。

2 面向有權網絡的社區劃分模型

2.1 團體間的連接強度度量準則

通過式(4)可以將單個節點合并成一個個小團體。然后需將這些小團體合并成大的團體直到形成一個個社區。如何合并這些小團體是社區劃分研究需要解決的一個關鍵問題。按照同一社區通常有較強凝聚性的原則，本文研究通過定義團體間的權值來刻畫團體間的連接強度。然后，依照權重值的大小來合并各個小團體直到形成合適的社區。兩個團體之間的權值基于任意兩個不在一個小團體內的節點的相關度的加權平均來計算，如式(5)所示。

(5)

其中，weight(Ci,Cj)表示小團體Ci和Cj之間的權值；σij表示小團體Ci和Cj之間任意兩個不在一個小團體內的節點的相關度。

2.2 算法描述

算法思想: 計算各個節點之間的節點相關度，按照設定的閾值合并不同的節點，形成一個個小團體；計算不同團體間的連接強度，不斷合并節點或小團體，迭代該過程直到找到合適的社區為止；通過評價指標對社區劃分結果進行評價。

算法流程: 假設G(V，E，W)是一個由n個節點m條邊組成的復雜網絡。其中V是網絡節點的集合，E是網絡邊的集合，W是網絡邊上權重的集合。

(1) 計算各個節點間的相關度，表示為σ。同時，根據σ的大小設定一個閾值T。

(2) 初始化社區，對于每個節點，將每個節點的社區分別表示為L{i}。

(3) 找到節點間相關度最大且其值大于閾值T的節點對，將其合并為小團體。如果節點vi和vj滿足條件，則將節點vj對應社區中節點移到vi對應的社區中，即L{i}=L{i,j}，并將L{j}清空，其相應的連接強度全部歸為0。

(4) 重復步驟(3)直到沒有找到滿足相關度(連接強度)最大和相關度(連接強度)大于閾值T的節點對為止。

(5) 計算由步驟(4)得到的團體L之間的連接強度W，找到最大W值所對應的團體進行合并。

(6) 重復步驟(5)，直到團體社區L的個數等于k時迭代終止，并計算相應的社區劃分的評價指標。

(7) 對不同類型的復雜網絡分別設定不同的k值，評價不同k值對應的社區劃分結果。

3 實驗結果與分析3.1 評價指標

為了評價該方法的社區劃分效果，本文實驗使用了2004年Newman[20]提出的Q函數概念，當模塊性Q函數最大時表示網絡劃分最好。在加權網絡中，Q函數通常按式(6)的形式計算。

(6)

其中，aij為網絡鄰接矩陣的元素，如果vi和vj兩節點相連，則aij為邊的權重，否則等于0；δ為隸屬函數， 當節點vi和vj屬于同一個社團時， 隸屬函數

為1，否則等于0；M=0.5*∑aij為網絡中邊的權重之和。在網絡劃分結構固定，兩節點的邊隨機連接時，節點間存在邊的可能性為kikj/(2M)，ki為節點vi的點權，計算方法為對鄰接矩陣的第i行求和。

3.2 實驗數據

本文使用兩個數據集驗證所提出的方法，包括: 科學家合作網絡和全國列車運行網絡數據集。實驗所用的科學家合作網絡[21]是由Mark Newman于2006年編寫的有權網絡，網絡節點表示網絡科學領域的科學家，邊表示科學家之間的論文合作關系，權值為作者間的直接合作數量。該版本的科學家合作網絡共有1 589名科學家，其中包括由379位科學家組成的最大社區。全國列車運行網絡數據收集了我國全部的列車數據和任意車次的途徑車站數據，為了消除部分特殊點本文的實驗中采用的列車運行網絡數據僅保留了五線城市以上的站點，并對一個城市中的所有站點進行了合并，構成了一個由273個節點和12 925條邊的加權復雜網絡，其中不同城市間的連邊權值由來往車次數和實際距離確定。兩組實驗數據的基本信息如表1所示。

表1 兩種實驗數據信息

3.3 基于科學家合作網絡的社區劃分

針對科學合作網絡數據集進行的實驗使用作者間的合作數據作為相似權，實驗表明當參數α，β分布選取0.6和0.4，且閾值T為2時得到最好的社區劃分結果，將整個網絡劃分為397個社區。此時各個子社區之間沒有連邊，模塊度達到0.81，最大的子社區包含節點數為379，表2顯示了該實驗的社區劃分結果。

表2結果顯示科學家合作網絡中存在很多零散的小社區。本文方法有效的將社區中由379位科學家組成的最大的子社區部分精確的找出來，并將其余的節點也很好的進行了社區劃分。其中，節點數在5以下的子社區數量占所有子社區數量的85.6%。該實驗表明本文提出的方法在科學家合作網絡數據集上會取得模塊度較大的社區劃分結果。

表2 基于科學家合作網絡數據集的社區劃分結果統計

3.4 基于列車運行網絡的社區劃分

(1) 社區發現實驗

在列車運行網絡數據集的實驗中本文分別將站點的來往次數作為相似權，站點間的距離作為相異權，并基于相異權和相似權的不同調節參數分別進行了社區劃分實驗。α，β采用了科學合作網絡實驗中結果最好的參數作為初始值，同時使用了其他參數值進行了同類實驗，并選擇了結果最好的參數值作為后續比較實驗的參數。各組實驗都選取α=0.6，β=0.4，并在T為0.035時取得較好的實驗結果。圖3～圖6展示了在不同的社區數，不同的x和y時對應的不同效果圖。由于節點較多實驗選出至少包括10個節點的較大的社區來展示劃分結果，并將各個較大社區包含的不同站點按照經緯度在圖中顯示出來。每個社區用不同的顏色來區分，橫坐標表示經度，縱坐標表示緯度。

實驗一7個較大社區時，不同相異權和相似權對應的社區劃分結果如圖3a～3c所示:

圖3a 只考慮站點間距離的社區劃分

圖3b x=0.9 y=0.1

圖3c x=0.8 y=0.2

實驗中在x=0.7和y=0.3時未找見7個較大社區。

實驗二6個較大社區時，不同相異權和相似權對應的社區劃分結果如圖4a～4d所示。

圖4a 只考慮站點間距離的社區劃分

圖4b x=0.9 y=0.1

圖4c x=0.8 y=0.2

圖4d x=0.7 y=0.3

實驗中，在x=0.6和y=0.4時，未找見6個較大社區。

實驗三5個較大社區時，不同相異權和相似權對應的社區劃分結果如圖5a～5e所示:

圖5a 只考慮站點間距離的社區劃分

圖5b x=0.9 y=0.1

圖5c x=0.8 y=0.2

圖5d x=0.7 y=0.3

圖5e x=0.6 y=0.4

實驗中，在x=0.5和y=0.5時，未找到5個較大社區。

實驗四4個較大社區時，不同相異權和相似權對應的社區劃分結果如圖6a～6e所示:

圖6a 只考慮站點間距離的社區劃分

圖6b x=0.9 y=0.1

圖6c x=0.8 y=0.2

圖6d x=0.7 y=0.3

圖6e x=0.6 y=0.4

實驗中，在x=0.5和y=0.5時，未找到4個較大社區。

(2) 實驗結果分析

圖3～圖6顯示出不同城市之間形成了較明顯的社區結構。對于只考慮站點間距離的社區劃分形成的圖3～圖6中的a圖，盡管形成了社區，但部分社區將離得較遠的節點劃分到一起了，出現這種現象的主要有兩個原因: ①部分節點只與較遠的節點有連邊； ②兩個節點之間的連邊權值，既考慮了直接連邊也考慮了共同鄰居節點的連邊。

對于圖3～圖6中的b、c、d、e圖，針對不同的社區數的社區劃分結構都有明顯的變化，但從圖中可以看出越到后邊的圖節點越稀疏，社區越清晰，越能看出列車運行網絡的骨干線路。出現這種現象主要是因為隨著連邊權值的調節參數不斷加大，節點之間的連邊數在社區劃分中起的作用越大，而相應的節點距離起的作用就會變小。這將會導致部分地理位置上比較緊密的點，可能由于來往次數比較少而成為了孤立節點或者較小的社區。

圖4a中6個大社區時的社區劃分對應的部分城市如表3所示，表4為考慮距離與來往次數比值為 7∶3時的社區劃分結果對應的城市列表，表5是兩者的交集結果。通過對這些數據的分析可以發現三類城市: ①部分城市距離較近，但他們之間的列車運行趟數較少，這些城市會隨著連邊次數的權值占比加大而逐漸分散； ②部分城市距離較遠，會隨著連邊次數的權值占比加大而逐漸聚合； ③部分城市不僅距離較近，他們之間的列車運行趟數也較多，屬于比較穩定的經濟體，如表5所示。同時，基于完整的社區發現數據還可進一步發現較小的社區和孤立點。

表3 只考慮距離的社區劃分結果對應的城市列表

表4 考慮距離與來往次數比值為7∶3時的社區劃分結果對應的城市列表

表5 表3和表4相交的城市列表

針對不同類型數據集上的實驗結果表明，本文提出的面向復雜有權網絡的社區發現方法具有較好的社區劃分效果。面向全國列車運行網絡數據集的實驗分析了全國列車城市站點的不同類別，挖掘了穩定的經濟體、節點較少的社區和孤立點等，可進一步為較大的經濟體的建設提供重要的依據。

4 結論

本文結合節點的直接連邊權重和基于共同鄰居節點的連邊權重提出了一種改進的節點相關度度量準則。基于這種改進的節點相關度度量準則和團體之間的聚集方法構建了面向有權網絡的社區發現模型。在有權值的科學家合作網絡和全國列車運行網絡數據集上進行了社區發現實驗，驗證了本文提出的方法在有權網絡的社區劃分上的有效性，分析了該方法在全國列車運行城市類別研究中的重要意義。接下來將在本文實驗的基礎上進一步面向復雜交通網絡研究最有影響力的城市節點發現方法和社區的“結構洞”挖掘模型。