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

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

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

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

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

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

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

(1) 充分利用了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息,為節(jié)點設(shè)計了不對稱的轉(zhuǎn)移概率,能夠反映節(jié)點間的不對等關(guān)系;

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

Table 1 Symbols and their remarks表1 相關(guān)符號及其注釋

2.1 整體框架

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

Fig.1 Framework of CDATP圖1 CDATP框架

框架包含以下兩個部分.

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

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

CDATP的描述見算法1.

算法1.CDATP.

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

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

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

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

但是,并非所有屬性都是有價值的.將節(jié)點的所有屬性直接加入計算不僅會降低計算效率,甚至可能因為在不同社區(qū)間產(chǎn)生了過多聯(lián)系而導(dǎo)致社區(qū)檢測準(zhǔn)確率下降.現(xiàn)在先考慮使用單個屬性.如圖3(a)所示,網(wǎng)絡(luò)中存在兩個社區(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)生負(fù)面影響;若考慮描述對象身份證號碼的屬性ID,則由于每個節(jié)點的ID的值都不一樣,如圖3(c)所示,節(jié)點間不會產(chǎn)生新的聯(lián)系,因此對社區(qū)的劃分同樣沒有幫助.

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

因此,需要選擇合適的屬性,這種屬性應(yīng)當(dāng)滿足下面兩個條件.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

得到影響力矩陣后,按公式(6)將矩陣每一行歸一化,即得到轉(zhuǎn)移概率矩陣P=(pij)N×N,pij為光標(biāo)從節(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ù)的計算方法.假設(shè)一個光標(biāo)依次從網(wǎng)絡(luò)中各個節(jié)點出發(fā),按照P中的轉(zhuǎn)移概率隨機選擇下一次轉(zhuǎn)移的目標(biāo)節(jié)點,每次出發(fā)后共轉(zhuǎn)移2次,取最后所在節(jié)點為終點.每個節(jié)點的核心系數(shù)corei即是該節(jié)點為終點節(jié)點的次數(shù)期望.同時,與一些經(jīng)典的基于random walk的方法一樣,本文設(shè)定光標(biāo)在每次轉(zhuǎn)移后有back幾率退回轉(zhuǎn)移前的節(jié)點.那些經(jīng)典的基于random walk的方法加入?yún)?shù)back通常是為了避免光標(biāo)的轉(zhuǎn)移在進(jìn)入某些特殊路徑后陷入死循環(huán),但本文提出方法的轉(zhuǎn)移次數(shù)固定且較小,幾乎不受這些特殊路徑的影響,加入?yún)?shù)back是為了能更好地模擬數(shù)據(jù)的傳播.設(shè)想某人在瀏覽網(wǎng)絡(luò)論壇時常常會因為對當(dāng)前頁面的內(nèi)容不感興趣而回退到上一級頁面,而類似的回退操作在其他場景中也時有發(fā)生,本文加入的參數(shù)back即蘊含了這類回退操作的含義.

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

在核心系數(shù)的基礎(chǔ)上,本文設(shè)計了一種不需要預(yù)先指定社區(qū)數(shù)目的聚類方法,在網(wǎng)絡(luò)中,每個節(jié)點都會按照該方法確定其聚類方向并和對應(yīng)的節(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)絡(luò)中邊的信息全部去除后的新網(wǎng)絡(luò),再按照下面的步驟添加邊.

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

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

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

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

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

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

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

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

3 實驗分析

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

3.1 實驗準(zhǔn)備

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

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

在第3.3節(jié)基于有向網(wǎng)絡(luò)的實驗中,本文使用了有向版本的PolBlogs數(shù)據(jù)集和LFR基準(zhǔn)網(wǎng)絡(luò)[26].構(gòu)造LFR基準(zhǔn)網(wǎng)絡(luò)使用的參數(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表示度序列的負(fù)指數(shù);t2表示社區(qū)規(guī)模分布的負(fù)指數(shù);mins表示社區(qū)節(jié)點數(shù)下限;maxs表示社區(qū)節(jié)點數(shù)上限.對于μ和N以外的參數(shù),本文使用了文獻(xiàn)[26]中的推薦取值.另外,本文參考了現(xiàn)有工作中對參數(shù)μ和N的設(shè)置[27],對于每一種μ和N的組合(對應(yīng)不同環(huán)境下的網(wǎng)絡(luò))都生成5個網(wǎng)絡(luò),累計起來一共是120個人工網(wǎng)絡(luò).實驗選擇ConClus,OSLOM和LP作為對比算法.

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

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

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

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

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

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

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

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

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

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

當(dāng)網(wǎng)絡(luò)按照標(biāo)記被劃分為兩個社區(qū)時,模塊度Q=0.396,并未達(dá)到最大值,因此,以模塊度為基礎(chǔ)的算法會繼續(xù)讓社區(qū)分裂,難以找到正確的社區(qū)數(shù)目.如圖8所示:當(dāng)back=0.1時,當(dāng)初始聚類結(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)絡(luò)及CDATP的社區(qū)劃分

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

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

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

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

圖12是各種算法的實驗結(jié)果對比.Karate和Dolphins是兩個典型的基準(zhǔn)社區(qū)結(jié)構(gòu)對應(yīng)較低質(zhì)量指標(biāo)的例子.Karate網(wǎng)絡(luò)和Dolphins網(wǎng)絡(luò)的基準(zhǔn)社區(qū)數(shù)量均為2,且當(dāng)它們的模塊度達(dá)到最大值時,都會被劃分為4個社區(qū),對應(yīng)的NMI較低,因此,基于優(yōu)化社區(qū)質(zhì)量指標(biāo)的社區(qū)發(fā)現(xiàn)算法在這樣的真實網(wǎng)絡(luò)上表現(xiàn)不佳.并且在Karate數(shù)據(jù)集中還存在著“雙峰結(jié)構(gòu)”[35],當(dāng)模塊度第1次到達(dá)極大值時,對應(yīng)的社區(qū)劃分質(zhì)量非常低,這也導(dǎo)致了一些基于社區(qū)質(zhì)量指標(biāo)的社區(qū)發(fā)現(xiàn)算法無法適應(yīng)這類網(wǎng)絡(luò).ISCD+在Karate網(wǎng)絡(luò)上的NMI雖然也達(dá)到了1,但需要通過大量的準(zhǔn)備實驗和專家知識來設(shè)定社區(qū)數(shù)量,實用性較弱.而CDATP是參考事件傳播規(guī)律設(shè)計的,對真實網(wǎng)絡(luò)的適應(yī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)絡(luò)是具有方向性的,但基于無向網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法直接將其作為無向網(wǎng)絡(luò)處理,所以各算法在該數(shù)據(jù)集上的表現(xiàn)均不是太好.這說明對于有向網(wǎng)絡(luò),當(dāng)忽略掉邊的方向性后,將丟失掉網(wǎng)絡(luò)中一些重要的信息.

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

Fig.11 Relation of NMI and back index圖11 NMI與back 的關(guān)系

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

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

有向版本的PolBlogs描述了邊的方向.與文獻(xiàn)[27]一樣,首先將網(wǎng)絡(luò)中的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)絡(luò)社區(qū)劃分NMI對比

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

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

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

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

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

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

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

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

4 結(jié)論及展望

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

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

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

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

進(jìn)一步的研究需要在以下3個方面展開.

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

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

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

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