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

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

社會網(wǎng)絡中的社區(qū)由網(wǎng)絡中一定數(shù)量的節(jié)點組成,其內(nèi)部有著較為緊密的結(jié)構(gòu).研究網(wǎng)絡中的社區(qū)結(jié)構(gòu)可以幫助分析復雜網(wǎng)絡、預測社會網(wǎng)絡的發(fā)展趨勢,而且在廣告投放和作弊用戶檢測等實際場景中得到應用.

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

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

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

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

(1) 充分利用了網(wǎng)絡拓撲結(jié)構(gòu)信息,為節(jié)點設計了不對稱的轉(zhuǎn)移概率,能夠反映節(jié)點間的不對等關系;

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

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

1 相關工作

近年來,普遍存在于網(wǎng)絡中的社區(qū)結(jié)構(gòu)已經(jīng)受到了國內(nèi)外學者的廣泛關注.關于社區(qū)發(fā)現(xiàn)的研究也已經(jīng)被應用到了許多領域中,并取得了不錯的成果.

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

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

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

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

2 社區(qū)發(fā)現(xiàn)算法CDATP

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

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

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

2.1 整體框架

圖1描述了CDATP進行社區(qū)檢測的整體框架,輸入數(shù)據(jù)集包括社交網(wǎng)絡等復雜社會網(wǎng)絡,輸出結(jié)果為社區(qū)序列.

Fig.1 Framework of CDATP圖1 CDATP框架

框架包含以下兩個部分.

(1) 在子空間構(gòu)造階段中找到表現(xiàn)最好的子屬性空間,并將相應的屬性轉(zhuǎn)化為網(wǎng)絡中的虛擬節(jié)點,構(gòu)造屬性增強網(wǎng)絡;

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

CDATP的描述見算法1.

算法1.CDATP.

2.2 子空間構(gòu)造和屬性增強圖

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

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

Fig.2 Virtual nodes圖2 虛擬節(jié)點

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

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

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

(1) 在結(jié)構(gòu)上聯(lián)系緊密的節(jié)點在該屬性上有相同屬性值的概率較大;

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

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

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

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

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

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

其中,αA是矩陣縮放因子,旨在更加明顯地區(qū)分屬性的結(jié)構(gòu)影響度.

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

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

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

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

2.3 聚類方向和社區(qū)劃分

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

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

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

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

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

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

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

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

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

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

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

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

Table 2 Sample of core index表2 節(jié)點核心系數(shù)示例

構(gòu)建一個將原網(wǎng)絡中邊的信息全部去除后的新網(wǎng)絡,再按照下面的步驟添加邊.

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

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

(3) 重復上述步驟,直到?jīng)]有度為0的節(jié)點.

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

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

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

圖5描述了圖3(a)網(wǎng)絡的社區(qū)發(fā)現(xiàn)過程.在新的網(wǎng)絡中,任意條邊兩端的節(jié)點都屬于同一社區(qū).

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

3 實驗分析

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

3.1 實驗準備

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

Table 3 Datasets of undirected network表3 無向網(wǎng)絡數(shù)據(jù)集

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

Table 4 Parameters of LFR表4 LFR參數(shù)

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

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

Table 5 Parameters of CDATP表5 CDATP參數(shù)

3.2 基于無向網(wǎng)絡的CDATP有效性驗證

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

Fig.6 Karate network and community division result of CDATP圖6 Karate網(wǎng)絡及CDATP的社區(qū)劃分

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

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

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

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

Fig.8 Dolphins network and community division result of CDATP圖8 Dolphins網(wǎng)絡及CDATP的社區(qū)劃分

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

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

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

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

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

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

Fig.10 PolBlogs network and community division result of CDATP圖10 PolBlogs網(wǎng)絡及CDATP的社區(qū)劃分

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

Fig.12 NMI comparison on real world undirected datasets圖12 社區(qū)劃分結(jié)果NMI對比

3.3 基于有向網(wǎng)絡的CDATP有效性驗證

有向版本的PolBlogs描述了邊的方向.與文獻[27]一樣,首先將網(wǎng)絡中的266個孤立節(jié)點除去.圖13展示了各算法實驗結(jié)果對比.算法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網(wǎng)絡社區(qū)劃分NMI對比

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

Fig.14 Influence of attribute enhancement network on results圖14 屬性增強網(wǎng)絡對結(jié)果的影響

這種現(xiàn)象的發(fā)生有兩個原因.

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

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

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

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

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

4 結(jié)論及展望

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

為了檢驗CDATP的表現(xiàn),本文做了大量實驗并得出了以下結(jié)論.

(1)Core指標正確地描述了節(jié)點在社區(qū)中的重要性,這說明基于網(wǎng)絡拓撲結(jié)構(gòu)設計的節(jié)點不對稱轉(zhuǎn)移概率充分體現(xiàn)了網(wǎng)絡中節(jié)點的不對等關系;

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

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

(1) 對于有權(quán)重網(wǎng)絡,如何利用邊的權(quán)重來構(gòu)建節(jié)點轉(zhuǎn)移概率;

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

(3) 研究如何根據(jù)不同網(wǎng)絡的特征來對本文中公式的參數(shù)進行相應的調(diào)整,以提高社區(qū)發(fā)現(xiàn)的準確率.

致謝在此,我們向?qū)Ρ疚牡墓ぷ鹘o予支持和建議的審稿人、主編、編輯、同行、同學和老師表示感謝.