節(jié)點(diǎn)不對(duì)稱轉(zhuǎn)移概率的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法?

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

2.1 整體框架

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

Fig.1 Framework of CDATP圖1 CDATP框架

框架包含以下兩個(gè)部分.

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

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

CDATP的描述見(jiàn)算法1.

算法1.CDATP.

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

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

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

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

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

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

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

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

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

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

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

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

本文構(gòu)造了屬性信息矩陣Y=(yij)N×N來(lái)描述虛擬節(jié)點(diǎn)對(duì)原節(jié)點(diǎn)間關(guān)系的影響,若節(jié)點(diǎn)vi與節(jié)點(diǎn)vj具有相同的屬性值,則yij=1;否則yij=0.另外,本文構(gòu)造了增量鄰接矩陣來(lái)描述加入了虛擬節(jié)點(diǎn)后新的網(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é)點(diǎn)間的聯(lián)系受到了多大的影響.Affect(Ai)可由公式(2)計(jì)算得到:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在現(xiàn)實(shí)世界中,無(wú)論是蟻群還是Reddit的興趣組,社區(qū)中的成員都并非完全平等,而是存在金字塔式的成員結(jié)構(gòu).受到社區(qū)中不平等現(xiàn)象的啟發(fā),為了評(píng)價(jià)節(jié)點(diǎn)在社區(qū)中是否處于金字塔頂端位置,本文引入了節(jié)點(diǎn)核心系數(shù)Core=(core1,core2,…,coreN)T,節(jié)點(diǎn)vi的核心系數(shù)corei越大,就越有可能成為社區(qū)的核心.現(xiàn)在介紹節(jié)點(diǎn)核心系數(shù)的計(jì)算方法.假設(shè)一個(gè)光標(biāo)依次從網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)出發(fā),按照P中的轉(zhuǎn)移概率隨機(jī)選擇下一次轉(zhuǎn)移的目標(biāo)節(jié)點(diǎn),每次出發(fā)后共轉(zhuǎn)移2次,取最后所在節(jié)點(diǎn)為終點(diǎn).每個(gè)節(jié)點(diǎn)的核心系數(shù)corei即是該節(jié)點(diǎn)為終點(diǎn)節(jié)點(diǎn)的次數(shù)期望.同時(shí),與一些經(jīng)典的基于random walk的方法一樣,本文設(shè)定光標(biāo)在每次轉(zhuǎn)移后有back幾率退回轉(zhuǎn)移前的節(jié)點(diǎn).那些經(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ò)論壇時(shí)常常會(huì)因?yàn)閷?duì)當(dāng)前頁(yè)面的內(nèi)容不感興趣而回退到上一級(jí)頁(yè)面,而類似的回退操作在其他場(chǎng)景中也時(shí)有發(fā)生,本文加入的參數(shù)back即蘊(yùn)含了這類回退操作的含義.

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

3.1 實(shí)驗(yàn)準(zhǔn)備

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)網(wǎng)絡(luò)按照標(biāo)記被劃分為兩個(gè)社區(qū)時(shí),模塊度Q=0.396,并未達(dá)到最大值,因此,以模塊度為基礎(chǔ)的算法會(huì)繼續(xù)讓社區(qū)分裂,難以找到正確的社區(qū)數(shù)目.如圖8所示:當(dāng)back=0.1時(shí),當(dāng)初始聚類結(jié)束后,只有節(jié)點(diǎn)“DN63”和“Oscar”被劃分到了錯(cuò)誤的社區(qū),此時(shí)的NMI值為0.780 3.以“DN63”為例,它同時(shí)和“Upbang”“SN9”這兩個(gè)核心系數(shù)較大的節(jié)點(diǎn)相連,而“SN9”的核心系數(shù)為1.356 8,略大于“Upbang”的1.308 7,所以“DN63”在聚類初始化時(shí)選擇了錯(cuò)誤的聚類方向,但是在邊緣修剪過(guò)程中,由于左邊社區(qū)對(duì)“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ù)集中的每個(gè)節(jié)點(diǎn)都代表一本美國(guó)的政治類書(shū)籍,如果有兩本書(shū)被同時(shí)從Amazon.com買走,則對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)間會(huì)有邊相連.書(shū)的類型按政治傾向分為“左派”“右派”和“中立派”這3類,其中,“中立派”數(shù)量最少.

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

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

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

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

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

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

有向版本的PolBlogs描述了邊的方向.與文獻(xiàn)[27]一樣,首先將網(wǎng)絡(luò)中的266個(gè)孤立節(jié)點(diǎn)除去.圖13展示了各算法實(shí)驗(yàn)結(jié)果對(duì)比.算法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對(duì)比

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

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

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

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

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

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

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

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

4 結(jié)論及展望

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

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

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

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

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

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

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

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

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