節點不對稱轉移概率的網絡社區發現算法?

許平華, 胡文斌, 邱振宇, 聶 聰, 唐傳慧, 高 曠, 劉中舟

(武漢大學 計算機學院,湖北 武漢 430072)

社會網絡中的社區由網絡中一定數量的節點組成,其內部有著較為緊密的結構.研究網絡中的社區結構可以幫助分析復雜網絡、預測社會網絡的發展趨勢,而且在廣告投放和作弊用戶檢測等實際場景中得到應用.

相關文獻中已經有很多種社區發現方法被提出,其中一類是優化與圖的拓撲結構相關聯的社區質量指標,例如由Newman等人[1]提出的模塊度.基于優化指標數值來獲得更加可靠的社區結構的這一思路,有很多學者提出了相關的社區發現算法,其中較為典型的有優化變體模塊度的BiLPA算法[2]、優化結構密度的IsoFdp算法[3]和對混合指標進行優化的EFA算法[4]、MOCD-PSO算法[5]等.這些算法一般是通過相應的迭代步驟來更新需要優化的指標,并在最后輸出最優指標對應的社區結構.這類算法的優點是實現簡單,在人工構造的網絡上可以發揮出很好的效果.然而真實世界的網絡要比人工構造的網絡復雜許多,很多時候真實社區結構對應的質量指標并不是最優的,導致了上述基于指標優化的算法難以正確地檢測到社區.同時,由于上述部分算法是基于全局拓撲結構來進行優化,因此會受到分辨率極限[6]的限制.并且,某些并不具有明顯社區結構的網絡同樣會具有很高的質量指標,例如某些樹或類樹結構[7].因此,這些缺陷都在一定程度上限制了上述方法的應用場景.

另外有一些學者從節點相似性的角度提出了基于random walk的社區發現方法[8?16],這類方法以馬爾可夫模型為理論基礎,通常是通過節點的隨機轉移來評估節點的相似度,并將相似度較高的節點劃分到同一社區中.在真實網絡中,同一社區質量指標與不同類型的社區結構的匹配程度變化較大,由此可能會導致基于社區質量指標的社區發現算法適應性較弱,而基于random walk的算法受社區類型的影響較小,具有更好的適應性.但是,基于“利用random walk來評價節點相似度”這一思路的社區發現算法對游走過程的迭代次數非常敏感,往往需要先驗知識來輔助決策.

將現實世界中的復雜系統抽象為圖論中的網絡雖然便于研究工作的開展,但也不可避免地會遺漏掉一些重要的信息.例如,Reddit中屬于同一興趣組的用戶往往有著相同的興趣標簽,若能將屬性信息轉化為網絡的一部分,可能會使得社區內部的結構更加緊密,也能使處于社區邊緣位置上的節點有更大概率被劃分到正確的社區中.然而,現有的僅從網絡結構層面劃分社區的算法無法利用節點的屬性信息.

基于以上分析,本文提出了一種可用于無向和有向網絡的社區發現算法CDATP(community detection algorithm based on asymmetric transition probability of nodes),此算法可以將節點的屬性轉化為拓撲結構的一部分,并且受到事件在網絡中的傳播規律的啟發,根據網絡的拓撲結構計算每一節點向鄰接節點轉移的概率,以帶有限制的random walk來模擬逆向的事件傳播過程,并以此為基礎,評估節點在社區中的重要程度(核心系數).在聚類時,無需預先指定社區的數目,節點會根據轉移概率等參數向所屬社區轉移.本文的主要工作可以總結如下:

(1) 充分利用了網絡拓撲結構信息,為節點設計了不對稱的轉移概率,能夠反映節點間的不對等關系;

(2) 參考了事件在網絡中傳播的規律,提出一種基于random walk且具有固定轉移步長的方法來評估節點對于社區的重要程度,基于該重要程度指標的聚類不需要預先指定社區數目.

本文第1節介紹相關研究工作.第2節詳細介紹CDATP算法.第3節為實驗和分析.第4節是總結與展望.

1 相關工作

近年來,普遍存在于網絡中的社區結構已經受到了國內外學者的廣泛關注.關于社區發現的研究也已經被應用到了許多領域中,并取得了不錯的成果.

基于社區質量指標來劃分社區是一類很經典的方法,這類方法通常先定義一個基于網絡拓撲結構的社區質量指標,若一種社區劃分與預先定義的質量指標的“含義”越接近(如社區內部的邊數遠多于社區邊緣上的邊數),那么該社區劃分的得分越高.這類方法的優點是思路簡潔明了,在確定了質量指標后只需通過一系列迭代運算來搜索最優社區劃分.但同時,如何確定社區質量指標也成了最大的問題.因為若一個社區質量指標不能較好地體現真實社區的“含義”,或者說一種社區劃分得分很高但卻與真實社區結構相差甚遠,那么基于該質量指標的后續工作都將變得沒有意義.經過長時間的研究,學者們提出了一些表現較好的經典社區質量指標,包括結構密度和模塊度等.結構密度的大小和社區內部邊的數量與社區內部節點的數量比值相關,一般來說,結構較為緊密的社區對應的結構密度較大.You等人[3]提出的IsoFdp算法將網絡數據映射到低維空間并自動找出社區的中心節點,然后再以中心節點為基礎建立社區,并通過對結構密度的優化來搜索更好的社區劃分.相較于傳統的基于結構密度的社區發現算法,IsoFdp的最大優勢是可以自動識別出社區的中心節點,有較好的可行性.模塊度的內涵是評價人工社區劃分與隨機社區劃分的差異性.Newman等人[17]提出的FastQ算法是最為經典的基于模塊度的社區發現算法,該算法以貪心策略進行分層聚類,其優點是收斂速度快,可以在較短時間內找到模塊度最大的社區劃分.雖然很多基于社區質量指標的社區發現算法在人工網絡上有很好的表現,但在處理真實網絡時,容易產生時好時壞的結果.這是因為真實網絡的度分布相較于人工網絡隨機性較大,社區質量指標有時與真實社區結構不匹配[18].為了減少這種不匹配帶來的問題,一些學者開始研究更小粒度的質量指標.Bai等人[19]提出的ISCD+算法中定義了針對節點的質量指標,包含節點的局部重要性和全局重要性.與傳統的社區質量指標不同,該指標并非是基于社區劃分,而是基于原始網絡中的每一個節點.實驗結果表明:在一些真實網絡上,該算法的表現優于部分基于社區質量指標的算法.受到現有的各類質量指標的啟發,本文嘗試定義一種新的基于節點的質量指標,并希望該指標能夠較好地適應不同類型的真實網絡.

將基于馬爾可夫模型的random walk用于社區發現也是較為主流的研究方法之一,其主要思想是以一個初始分布釋放大量的無規則行走者,在擴散過程之后,可以得到行走者的分布函數.通過一系列研究,國內外學者提出了若干種基于random walk的社區發現算法.Pons等人[8]提出的Walktrap算法是最早的基于random walk的方法之一,該算法的主要思想類似于“在社區結構中,節點間有著更多的聯系,而不同社區間的聯系則相對較少.因此,一個隨機選擇方向的行走者將會被更長時間地困在社區內部[20]”.Walktrap算法采用了分層聚類的方式發現社區,得到的社區有很清晰的層級結構.雖然Walktrap算法在準確度上有所欠缺,但該算法的思路對于后來的同類型算法有很強的啟發作用.Lai等人[9]通過將邊的方向信息轉化為邊的權重實現了將有向網絡轉化為無向網絡,并進一步通過基于無向網絡的算法來發現原來的有向網絡中的社區.該算法處理邊的方向信息的方式很新穎,且在基于有向網絡的社區發現問題中取得了不錯的效果,但轉化過程計算量較大,且不適用于基于無權值網絡算法的拓展.Jiao等人[10]綜合考慮了全局拓撲結構和局部拓撲結構,并在此基礎上提出了新的節點相似度計算方法,與以往算法相比,對不同類型社區的適應性更強.Huang等人[11]提出的SCMAG算法通過計算節點屬性相似度來從節點屬性的角度構建社區,并證明了節點屬性與社區結構之間存在密切的聯系,屬于同一社區的節點往往具有相似的屬性.本文受其啟發,嘗試以將節點屬性轉化為拓撲結構信息的方式來處理節點屬性.此外,文獻[12?16]各自提出了將random walk與其他經典方法進行融合得到的社區發現算法,在一些特定的網絡模型上有較好的表現.然而,上述算法在節點轉移的步驟中多采用的是無差別轉移概率,不能完全反映真實網絡中節點關系的不對稱性,且社區劃分的準確性受轉移迭代次數影響較大,需要較多的先驗知識來輔助決策;同時,本文認為,由于random walk在模擬隨機過程等方面具備一些優良的特性,可以將其作相應改進后用于評價節點的質量指標,而在目前的工作中,尚未發現有人進行過這樣的嘗試.

在社區發現領域的研究初期,大部分學者都是以無向網絡作為研究對象.但隨著社區發現技術在實際生產情景中的應用推廣,有越來越多的學者開始關注如何在有向網絡中發現社區.早期的一種處理方法是忽略掉邊的方向,將其直接作為無向網絡來處理.例如,將經典的基于無向網絡的LP算法[21]直接用于忽略了邊的方向的有向網絡,在某些情況下仍有不錯的準確率,可用作對有向網絡算法測試的基線.但文獻[22]中指出:邊的方向應該被考慮,否則會使得網絡的重要特征丟失.其中一個重要原因就是:當忽略了邊的方向后,節點間的相互關系將變得不完整.例如,Twitter中的某一用戶單方面關注了另一用戶,那他們之間的位置是不平等的,但無向邊無法描述這種關系.一部分學者根據有向網絡的特征重新設計了質量指標,例如,Newman等人[23]提出了有向版本的模塊度,在原來的模塊度定義的基礎上考慮了邊的方向信息,是最早的基于有向網絡的社區質量指標之一.Rosvall等人[24]基于信息論提出了Infomap算法,該算法根據網絡的拓撲結構來預測數據的流動,然后對其進行信息編碼,而平均長度最短的編碼方式就對應了最優的社區劃分.得益于其簡潔而優美的設計思路,Infomap算法可被用于處理各種不同類型的網絡,且均有不錯的表現.Lancichinetti等人[25]提出的OSLOM算法是另一個非常經典的可用于有向網絡的社區發現算法,它使用了一個基于簇的質量指標來評價人工劃分得到的簇與隨機生成的簇之間的差異,并通過局部優化來找到得分較高的簇,最后基于這些簇來生成社區.Lancichinetti等人對網絡中的度分布有較深入的研究,并且開發了基于冪分布的基準網絡[26]用于檢驗社區發現算法的準確性,而OSLOM算法也在人工網絡上有非常好的表現.Santos等人[27]基于改進后的模塊度提出了ConClus算法,該算法規避了傳統的模塊度優化算法常常會碰到的分辨率極限問題.實驗結果表明,ConClus在人工有向網絡上有與OSLOM十分相近的表現,且在真實網絡上也有不錯的表現.上述的可用于有向網絡的社區算法一般在人工網絡上有較高的準確率,但在一些真實網絡上,其準確率仍有較大的提升空間.因此,提高算法在真實網絡上的準確率也是本文嘗試去實現的目標之一.

受到現有的社區發現算法的優勢及缺陷的啟發,本文參考了網絡中的事件傳播規律,提出一種基于random walk的方法來評價節點對社區的重要程度.與現有的基于random walk的節點相似度評價方法不同,本文設計了基于拓撲結構的不對稱節點轉移概率,并嘗試從模擬事件傳播的角度來評價節點對社區的重要程度而非節點相似度,且轉移過程具有固定的步長,不需要額外的先驗知識的輔助.最后,本文在該評價方法的基礎上提出了一種不需要預先指定社區數量,且在真實數據集和人工數據集上都能有較好表現的網絡社區發現算法.

2 社區發現算法CDATP

CDATP算法基于random walk方法來計算節點屬性相似性、節點間影響力,并以此為基準評估節點對社區重要程度,最后使節點向社區核心靠攏來劃分社區.

為使下文的描述簡潔,本文將研究對象的相關重要概念進行符號化定義,見表1.

Table 1 Symbols and their remarks表1 相關符號及其注釋

2.1 整體框架

圖1描述了CDATP進行社區檢測的整體框架,輸入數據集包括社交網絡等復雜社會網絡,輸出結果為社區序列.

Fig.1 Framework of CDATP圖1 CDATP框架

框架包含以下兩個部分.

(1) 在子空間構造階段中找到表現最好的子屬性空間,并將相應的屬性轉化為網絡中的虛擬節點,構造屬性增強網絡;

(2) 在社區劃分階段中,以屬性增強網絡為對象計算節點轉移概率,使用random walk方法評估節點核心系數,在此基礎上確定每個節點的聚類方向,創建初始社區,再進行邊緣修剪,最終輸出社區序列Comms.

CDATP的描述見算法1.

算法1.CDATP.

2.2 子空間構造和屬性增強圖

“物以類聚,人以群分”.人們通常會依其興趣愛好、工作內容來發展社交圈,而各種物件也能被按照其特性、功能劃分類別,屬性是對象間建立起聯系的重要“橋梁”.與研究高度抽象的網絡不同,在研究現實世界中更為復雜的情景時,若忽略了節點本身具備的屬性,很可能就會錯過一些重要的信息.屬于同一社區的節點往往擁有某些相近甚至相同的屬性值,在考慮這些屬性后,能更科學地度量節點間聯系的強弱,使得社區的邊界變得更加清晰,同時還能夠從節點屬性的角度幫助挖掘社區結構形成的原因.

為了度量屬性對節點間聯系的影響,本文采用了將屬性轉化為網絡中的虛擬節點來構造屬性增強網絡的方法.對于屬性Ai,若離散化后有Dom(Ai)={a1,a2,…,ak},則在圖中加入k個虛擬節點,與Ai的取值一一對應,并在原網絡節點與其對應屬性值的虛擬節點間建立一條雙向邊,如圖2所示,擁有相同屬性值的節點以虛擬節點為中介(虛擬節點可視為邊的一部分而非獨立的節點)產生了新的聯系.

Fig.2 Virtual nodes圖2 虛擬節點

但是,并非所有屬性都是有價值的.將節點的所有屬性直接加入計算不僅會降低計算效率,甚至可能因為在不同社區間產生了過多聯系而導致社區檢測準確率下降.現在先考慮使用單個屬性.如圖3(a)所示,網絡中存在兩個社區C1和C2,C1和C2之間聯系非常少.若考慮描述對象性別的二元屬性sex,則C1和C2之間sex值相同的節點(假定有這樣的節點對存在)間就會產生聯系,如圖3(b)所示,這種聯系的數量是很多的,破壞了C1和C2較為獨立的狀態,對社區劃分的結果產生負面影響;若考慮描述對象身份證號碼的屬性ID,則由于每個節點的ID的值都不一樣,如圖3(c)所示,節點間不會產生新的聯系,因此對社區的劃分同樣沒有幫助.

Fig.3 An example of an attribute enhancement network圖3 屬性增強網絡的示例

因此,需要選擇合適的屬性,這種屬性應當滿足下面兩個條件.

(1) 在結構上聯系緊密的節點在該屬性上有相同屬性值的概率較大;

(2) 在考慮該屬性之后,不同社區間應盡可能少地產生新的聯系.

而且,只有一個屬性相同往往不能說明節點間就有很強的聯系,考慮的屬性數目越多,則屬性值相同的偶然性越小,考慮包含多個屬性的子屬性空間相較于考慮單個屬性更加可靠.將子屬性空間中的所有屬性看作一個復合屬性,它同樣應該滿足前面提到的兩個條件.

信息熵可以理解為特定信息的出現概率.對于屬性Ai,若Dom(Ai)={a1,a2,…,ak},且對應屬性值為ai的節點個數為ni,則其信息熵H(Ai)可用公式(1)計算:

由于不存在重復的取值,所以前文中提到ID屬性的信息熵非常大,而這樣的屬性是沒有意義的,因此不應將信息熵超過閾值ht的屬性加入子屬性空間.

本文構造了屬性信息矩陣Y=(yij)N×N來描述虛擬節點對原節點間關系的影響,若節點vi與節點vj具有相同的屬性值,則yij=1;否則yij=0.另外,本文構造了增量鄰接矩陣來描述加入了虛擬節點后新的網絡拓撲結構,若yij與wij之和不為0,則

在此基礎上,本文定義了屬性的結構影響度Affect(Ai).屬性的結構影響度應能反映在將屬性信息轉化為拓撲結構信息后,原節點間的聯系受到了多大的影響.Affect(Ai)可由公式(2)計算得到:

其中,αA是矩陣縮放因子,旨在更加明顯地區分屬性的結構影響度.

子屬性空間應同時滿足信息熵較小和結構影響度較小的條件,其構造步驟如下.

(1) 計算每個屬性的信息熵,并篩除信息熵大于閾值ht的屬性;

(2) 計算剩余屬性的結構影響度,并選擇結構影響度小于閾值at且信息熵最小的屬性加入子屬性空間;

(3) 將剩余屬性按信息熵從小到大排序,若其中的屬性加入子屬性空間后,使得子屬性空間的信息熵和結構影響度均小于閾值,則將其加入子屬性空間.

2.3 聚類方向和社區劃分

由于缺少先驗知識,需要預先指定社區數目的聚類方法往往難以在社區發現中取得良好效果.為了能夠得到更加準確的社區結構,本文提出了一種自動確定社區的核心,并使核心以外的節點按照各自的聚類方向向核心靠攏的聚類方法,由此得到的社區不僅內部聚合度高,并且有著很清晰的層次結構,便于對社區中的事件傳播過程做進一步的研究.

文獻[28]指出,一個節點的狀態有一定概率會因其鄰接節點的行為而發生改變.若一個光標可從一個節點向它的任意鄰接節點轉移,且傾向于向有更大概率會對其狀態產生影響的節點轉移,那么在進行一定次數的轉移后,光標會有較大的概率落到事件傳播流中原節點的上游位置.而由于事件在傳播過程中,其影響力會呈現衰退的趨勢,本文參考了文獻[28]中的實驗結果,設定光標在尋找上游的過程中,將轉移2次.

本文構造了節點影響力force的概念來描述任意節點的鄰接節點會對其產生的影響,并假定該影響是由拓撲結構中的出鏈與入鏈以及節點間相同的屬性產生的.

記forceij為節點vj對節點vi的影響力,,其中,是由節點vi指向節點vj的出鏈產生的影響力,是由節點vj指向節點vi的入鏈產生的影響力,是由屬性關系產生的影響力.

以微博為例,如圖4所示,邊的寬度代表影響力的大小,關注關系和粉絲關系可由網絡中的有向邊表示,屬性關系可由原節點與虛擬節點的聯系表示.若用戶A關注了用戶B,說明B產生的內容對A有一定的的影響力.A接收到的內容信息量與其關注的總人數有關,人數越多,信息量越大,B產生的內容的信息量占比就小,對A產生的吸引力也會變弱;相反地,當A關注人數較少時,B對A的影響力會更強.同時,由于A成為了B的粉絲,B因為這種關系,也會在一定程度上被A產生的內容吸引,同樣的,影響力的強弱與B的粉絲數有一定關系,不過這種影響力的大小遠小于由關注關系產生的影響力大小.此外,由屬性產生的新關系同樣會作用于影響力,本文假定其大小介于前兩者之間.子屬性空間包含的屬性數目越多,則A與B擁有相同屬性值就越不可能是偶然發生的,由屬性產生的影響力就越大.類似的,在子屬性空間下,擁有相同屬性值的節點越多,則該子屬性空間越有可能與社區特征相關,由此產生的影響力也越大.本文進行了大量的預實驗,試圖找到最能體現節點間關系的影響力模型.由于篇幅的限制,本文不對建立影響力模型過程中的相關預實驗作展開說明.

Fig.4 Influence of outbound link,inbound link and attribute圖4 出鏈、入鏈、屬性與影響力的關系

根據預實驗的結果,本文使用了以自然常數e為底的指數函數來描述的變化,它們的計算公式分別為公式(3)和公式(4),其中,αout和αin分別為出鏈和入鏈系數,用于控制函數的收斂速度:

得到影響力矩陣后,按公式(6)將矩陣每一行歸一化,即得到轉移概率矩陣P=(pij)N×N,pij為光標從節點vi向節點vj轉移的概率:

在現實世界中,無論是蟻群還是Reddit的興趣組,社區中的成員都并非完全平等,而是存在金字塔式的成員結構.受到社區中不平等現象的啟發,為了評價節點在社區中是否處于金字塔頂端位置,本文引入了節點核心系數Core=(core1,core2,…,coreN)T,節點vi的核心系數corei越大,就越有可能成為社區的核心.現在介紹節點核心系數的計算方法.假設一個光標依次從網絡中各個節點出發,按照P中的轉移概率隨機選擇下一次轉移的目標節點,每次出發后共轉移2次,取最后所在節點為終點.每個節點的核心系數corei即是該節點為終點節點的次數期望.同時,與一些經典的基于random walk的方法一樣,本文設定光標在每次轉移后有back幾率退回轉移前的節點.那些經典的基于random walk的方法加入參數back通常是為了避免光標的轉移在進入某些特殊路徑后陷入死循環,但本文提出方法的轉移次數固定且較小,幾乎不受這些特殊路徑的影響,加入參數back是為了能更好地模擬數據的傳播.設想某人在瀏覽網絡論壇時常常會因為對當前頁面的內容不感興趣而回退到上一級頁面,而類似的回退操作在其他場景中也時有發生,本文加入的參數back即蘊含了這類回退操作的含義.

表2為當back=20%時,圖3(a)中節點的核心系數.可以看出,處于社區中心位置的節點往往具有非常高的核心系數,這與社區中的金字塔結構也是相對應的.

在核心系數的基礎上,本文設計了一種不需要預先指定社區數目的聚類方法,在網絡中,每個節點都會按照該方法確定其聚類方向并和對應的節點聚合到一起.

節點的聚類方向Dir=(dir1,dir2,…,dirN)T由轉移概率和核心系數共同決定,若pij為轉移概率矩陣P第i行的唯一最大值,則節點vi的聚類方向為diri=j;若等于最大值的元素有多個,則取其中核心系數最大的作為聚類方向.

Table 2 Sample of core index表2 節點核心系數示例

構建一個將原網絡中邊的信息全部去除后的新網絡,再按照下面的步驟添加邊.

(1) 從節點序列中取出核心系數最大的節點vi,若vi未與任何邊相連,則將該節點作為新社區的中心,并將其聚類方向記為空;

(2) 掃描Dir,若有節點vj未與任何邊相連且聚類方向dirj=i,則建立一條由節點vj指向節點vi的有向邊;

(3) 重復上述步驟,直到沒有度為0的節點.

這樣就得到了初始社區,下面再繼續進行邊緣修剪工作.

(1) 對于網絡中的每一個節點,計算其所屬社區中它的鄰接節點的核心系數之和,再計算其他社區中它的鄰接節點的核心系數之和,并將最大的核心系數之和對應的社區標記為節點新的所屬社區,但暫時不將節點劃入到新的社區當中;

(2) 在得到所有節點對應的新社區后,將所有節點劃入新社區當中,若有節點的所屬社區發生了改變,則重復(1)的工作,否則停止.

圖5描述了圖3(a)網絡的社區發現過程.在新的網絡中,任意條邊兩端的節點都屬于同一社區.

Fig.5 Example of community partitioning process圖5 社區劃分過程示例

3 實驗分析

本節通過在多個社會網絡數據集上的實驗來驗證CDATP算法的有效性.第3.1節為實驗準備部分,介紹了實驗中使用的各類型的數據集、對比算法、CDATP的參數設置和實驗結果評價標準.本文將實驗按照使用到的數據集類型分為兩部分,其中,基于無向網絡的實驗將在第3.2節中詳細介紹,基于有向網絡的實驗將在第3.3節中詳細介紹.

3.1 實驗準備

在第3.2節基于無向網絡的實驗中,本文共使用了Karate[29],Dolphins[30],PolBooks[31],PolBlogs[32]這4個帶基準的真實網絡數據集(http://networkdata.ics.uci.edu/),表 3介紹了這些數據集的相關特征信息.實驗選擇ISCD+,ROCONA[33],InfoMap和FastQ算法作為對比算法.其中,ROCONA算法是基于信息粒度觀點的最新社區發現算法,通過節點之間的關聯度來構建社區.ROCONA算法通過與其他對比算法不同的視角來發現網絡中的社區,且有較好的表現,因此本文也將其作為對比算法.

Table 3 Datasets of undirected network表3 無向網絡數據集

在第3.3節基于有向網絡的實驗中,本文使用了有向版本的PolBlogs數據集和LFR基準網絡[26].構造LFR基準網絡使用的參數見表4,其中:N表示節點總數;μ表示社區間邊數與內部邊數的比值,μ的值越大,則社區結構越模糊;k表示社區內平均節點度;maxk表示社區內最大節點度;t1表示度序列的負指數;t2表示社區規模分布的負指數;mins表示社區節點數下限;maxs表示社區節點數上限.對于μ和N以外的參數,本文使用了文獻[26]中的推薦取值.另外,本文參考了現有工作中對參數μ和N的設置[27],對于每一種μ和N的組合(對應不同環境下的網絡)都生成5個網絡,累計起來一共是120個人工網絡.實驗選擇ConClus,OSLOM和LP作為對比算法.

Table 4 Parameters of LFR表4 LFR參數

在第3.2節和第3.3節中所使用的數據集均是帶有基準信息的,因此本文使用NMI[34]評價實驗結果.NMI=1時,說明實驗結果與基準信息完全一樣.NMI的值越大,說明社區劃分的準確度越高.公式(7)是NMI的計算公式:

表5中介紹了CDATP的參數設置.在預實驗中,本文發現:在較小規模(包含的節點數小于5 000)的網絡中,與force相關的3個收斂因子取表5給出的預設值時準確度較高,且在預設值附近的小范圍變動對社區劃分的準確度影響非常小.受篇幅限制,本文在后面的實驗中對收斂因子的取值不作展開討論.參數back對實驗的準確度有一定影響,在第3.2節和第3.3節中,本文針對不同的back取值進行了實驗并對實驗結果進行了比較.

Table 5 Parameters of CDATP表5 CDATP參數

3.2 基于無向網絡的CDATP有效性驗證

Karate數據集是Zachary對一個美國大學空手道俱樂部進行了2年觀察而構建出的一個社會網絡,它被廣泛應用于社區檢測方法的測試.網絡中的節點表示俱樂部中的成員,而邊表示成員之間的朋友關系.由于俱樂部中一名管理人員和一名教練的矛盾,導致俱樂部分裂成了兩個派系.圖6描述了該網絡的拓撲結構,節點的顏色對應基準信息中的兩個社區.紫色虛線表示CDATP初始社區劃分,紅色虛線表示邊緣修剪引發的節點轉移.

Fig.6 Karate network and community division result of CDATP圖6 Karate網絡及CDATP的社區劃分

圖7是不同back取值下各節點Core的平均值,可以觀察到,節點1和節點34的Core總是最大或第二大的.而在現實世界中,節點1和節點34分別對應兩個派系的領導[29],因此他們處于社區的核心位置,所以對應的Core才會較大.CDATP的節點對社區重要程度的評價方法能很好地適應真實網絡條件.

Fig.7 Core index of nodes in Karate network圖7 Karate中各節點的Core

Dolphins數據集共包含62個節點和159條無向邊.網絡中的每個節點代表一只寬吻海豚,被每條邊連接起來的兩節點對應的海豚間有頻繁的互動.如圖8所示,網絡中原本有兩個社區,以節點的顏色作為區分,綠色虛線是CDATP的初始社區劃分,紫色虛線表示邊緣修剪引發的節點轉移.

當網絡按照標記被劃分為兩個社區時,模塊度Q=0.396,并未達到最大值,因此,以模塊度為基礎的算法會繼續讓社區分裂,難以找到正確的社區數目.如圖8所示:當back=0.1時,當初始聚類結束后,只有節點“DN63”和“Oscar”被劃分到了錯誤的社區,此時的NMI值為0.780 3.以“DN63”為例,它同時和“Upbang”“SN9”這兩個核心系數較大的節點相連,而“SN9”的核心系數為1.356 8,略大于“Upbang”的1.308 7,所以“DN63”在聚類初始化時選擇了錯誤的聚類方向,但是在邊緣修剪過程中,由于左邊社區對“DN63”有更大的吸引力,所以“DN63”轉移到了左邊的也即正確的社區中.

Fig.8 Dolphins network and community division result of CDATP圖8 Dolphins網絡及CDATP的社區劃分

PolBooks數據集中的每個節點都代表一本美國的政治類書籍,如果有兩本書被同時從Amazon.com買走,則對應的兩個節點間會有邊相連.書的類型按政治傾向分為“左派”“右派”和“中立派”這3類,其中,“中立派”數量最少.

CDATP的社區劃分結果以紫色虛線形式在圖9中標出,橙色代表“右派”,綠色代表“左派”,淺藍色代表“中立派”,紅色虛線表示邊緣修剪引發的節點轉移.CDATP識別出了兩個最大的社區,并且只有很少量“保守派”節點被劃分錯誤,但CDATP沒有識別出包含節點數量最少的“中立派”社區,而是將其分散到了另外兩個大的社區當中,這是由于“中立派”書籍總是與其他類型的書籍被一起購買,而不同“中立派”書籍間聯系又比較少導致的.

PolBlogs網絡是圍繞2004年美國總統大選時的政治類型博客建立的,其中的每個節點代表一個博客,按政治傾向分為“左派”和“右派”,節點間的邊代表博客間的超鏈接,與對比算法一樣,CDATP將其作為無向邊處理.由于節點數目太多,在圖10中使用了超節點來表示社區,其中,淺藍色代表“左派”,深藍色代表“右派”,其大小和包含節點的數目成正比,虛線上標的數字為邊緣修剪時的轉移節點數,而孤立節點未在圖中標出.從圖中可以看到,使用CDATP算法劃分社區后,只有少量的節點被錯誤劃分.

如圖11所示,本文在實驗中測試了不同back值的條件下,CDATP聚類初始化和邊緣修剪完成后的聚類效果.由于PolBlogs數據集中有266個節點未與其他節點產生聯系,所以理論上最大NMI為0.666 3.可以看出,除了在PolBooks數據集中部分情況下,邊緣修剪后導致NMI有小幅度下降,大多數情景中,邊緣修剪都能使NMI有一個不錯的提升.在Dolphins網絡中,當back超過0.1時,NMI出現了下降.這是因為此時檢測到的社區數由2變成了3,原來的兩個社區中較大的一個出現了分裂,而在其他情況下,算法準確度對back的變化并不敏感,邊緣修剪步驟很好地提升了初始社區的質量.

圖12是各種算法的實驗結果對比.Karate和Dolphins是兩個典型的基準社區結構對應較低質量指標的例子.Karate網絡和Dolphins網絡的基準社區數量均為2,且當它們的模塊度達到最大值時,都會被劃分為4個社區,對應的NMI較低,因此,基于優化社區質量指標的社區發現算法在這樣的真實網絡上表現不佳.并且在Karate數據集中還存在著“雙峰結構”[35],當模塊度第1次到達極大值時,對應的社區劃分質量非常低,這也導致了一些基于社區質量指標的社區發現算法無法適應這類網絡.ISCD+在Karate網絡上的NMI雖然也達到了1,但需要通過大量的準備實驗和專家知識來設定社區數量,實用性較弱.而CDATP是參考事件傳播規律設計的,對真實網絡的適應性更強,因此表現較好.

在PolBooks數據集中,由于“中立派”書籍總是和其他類型書籍被一起購買,所以“中立派”社區內部邊的數目明顯小于與其他社區之間邊的數目,社區結構非常松散.CDATP在該數據集上劃分正確的節點數目最多,但由于沒有將“中立派”單獨劃分為一個社區,所以NMI略低于ROCONA.PolBlogs數據集描述的網絡是具有方向性的,但基于無向網絡的社區發現算法直接將其作為無向網絡處理,所以各算法在該數據集上的表現均不是太好.這說明對于有向網絡,當忽略掉邊的方向性后,將丟失掉網絡中一些重要的信息.

Fig.10 PolBlogs network and community division result of CDATP圖10 PolBlogs網絡及CDATP的社區劃分

Fig.11 Relation of NMI and back index圖11 NMI與back 的關系

Fig.12 NMI comparison on real world undirected datasets圖12 社區劃分結果NMI對比

3.3 基于有向網絡的CDATP有效性驗證

有向版本的PolBlogs描述了邊的方向.與文獻[27]一樣,首先將網絡中的266個孤立節點除去.圖13展示了各算法實驗結果對比.算法ConClus,OSLOM和LP的NMI分別為0.678 9,0.572 1和0.385 3,均低于CDATP的NMI.

Fig.13 Comparison of NMI on PolBlogs network圖13 PolBlogs網絡社區劃分NMI對比

在源數據中,每個博客都是從博客檢索網站得到的.這些博客檢索網站包括Blogarama,LeftyDirectory等,一共有6個.如圖14所示:若將每個博客的檢索源作為屬性構造屬性增強圖,其聚類結果的NMI比未使用屬性時提高了9.8%,說明了屬性增強網絡在提高社區劃分準確度上的有效性,但同時也應注意到,準確度的提升并不是非常大.

Fig.14 Influence of attribute enhancement network on results圖14 屬性增強網絡對結果的影響

這種現象的發生有兩個原因.

· 一是大多數博客的檢索源都是Blogarama,而Blogarama并沒有明顯的政治傾向,其中包含的兩種政治傾向的博客數量基本持平,所以不會對結果造成什么影響;

· 二是因為某一些檢索源雖然有非常明確的政治傾向,如LeftyDirectory中基本全是“左派”博客,但對應這些檢索源的博客數量又相對較少,所以只能使結果的NMI有小幅度的上升.

圖15介紹了在不同參數的人工網絡中各算法的表現.如圖所示,ConClus,OSLOM和LP的準確度對數據集規模比較敏感.當數據集規模增大時,上述算法劃分社區的準確度會有小幅提升.而CDATP的準確度幾乎不受數據集規模的影響,在各種條件下都有較好的表現.由此可以看出,CDATP在人工構造的網絡中同樣有很好的表現且適應性較強.

Fig.15 NMI of different algorithms on LFR benchmark network圖15 LFR基準網絡上的算法NMI對比

Fig.15 NMI of different algorithms on LFR benchmark network (Continued)圖15 LFR基準網絡上的算法NMI對比(續)

4 結論及展望

為了能夠在各種類型的社會網絡中準確地劃分社區,本文提出了一種新的基于節點不對稱轉移概率的社區發現算法CDATP.CDATP為每個節點設計了不對稱的轉移概率,并結合事件傳播規律來對節點在社區中的重要程度進行評價.在聚類過程中,節點會根據轉移概率等信息自發地確定轉移方向,不需要預先設定社區數目.

為了檢驗CDATP的表現,本文做了大量實驗并得出了以下結論.

(1)Core指標正確地描述了節點在社區中的重要性,這說明基于網絡拓撲結構設計的節點不對稱轉移概率充分體現了網絡中節點的不對等關系;

(2) 在真實數據集上,CDATP有著非常好的表現,無需通過額外的實驗和專家知識指定轉移迭代次數.這說明基于事件傳播規律的聚類方法能夠很好地適應較為復雜的真實社會網絡.

進一步的研究需要在以下3個方面展開.

(1) 對于有權重網絡,如何利用邊的權重來構建節點轉移概率;

(2) 節點的聚類方向可以不限于1個,特別是對社區邊緣的節點.可以對確定聚類方向的流程加以改進,以發現重疊社區;

(3) 研究如何根據不同網絡的特征來對本文中公式的參數進行相應的調整,以提高社區發現的準確率.

致謝在此,我們向對本文的工作給予支持和建議的審稿人、主編、編輯、同行、同學和老師表示感謝.