基于節(jié)點(diǎn)向量表達(dá)的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法*

韓忠明,劉 雯,李夢(mèng)琪,鄭晨燁,譚旭升,段大高

1(北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,北京 100048)

2(食品安全大數(shù)據(jù)技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室,北京 100048)

1 引 言

如何準(zhǔn)確、高效地進(jìn)行社團(tuán)結(jié)構(gòu)劃分是當(dāng)前復(fù)雜網(wǎng)絡(luò)理論研究領(lǐng)域中的熱點(diǎn)問(wèn)題.很多復(fù)雜的系統(tǒng)可以轉(zhuǎn)化為由節(jié)點(diǎn)和邊組成的網(wǎng)絡(luò)來(lái)進(jìn)行建模,如人與人之間的關(guān)系網(wǎng)絡(luò)、科學(xué)家之間的合作網(wǎng)絡(luò)、學(xué)術(shù)論文間相互引用網(wǎng)絡(luò)、蛋白質(zhì)交互網(wǎng)絡(luò)和 WWW 鏈接網(wǎng)絡(luò)等.網(wǎng)絡(luò)中一個(gè)十分重要的性質(zhì)是社團(tuán)結(jié)構(gòu),理解社團(tuán)結(jié)構(gòu)對(duì)理解網(wǎng)絡(luò)的整體具有重要價(jià)值.Newman把社團(tuán)結(jié)構(gòu)定義為網(wǎng)絡(luò)中的若干個(gè)群體或者團(tuán)體,群體內(nèi)部的節(jié)點(diǎn)間存在緊密連接,群體間的連接則相對(duì)稀疏[1].

復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分對(duì)人們了解真實(shí)的網(wǎng)絡(luò)信息具有非常重要的意義.社團(tuán)是由復(fù)雜網(wǎng)絡(luò)中具有相同性質(zhì)的個(gè)體組成,例如萬(wàn)維網(wǎng)中的社團(tuán)可以是提供相似內(nèi)容的網(wǎng)站,蛋白質(zhì)網(wǎng)絡(luò)中的社團(tuán)可以是具有相似功能的基因.發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)可以幫助人們了解復(fù)雜系統(tǒng)的拓?fù)湫再|(zhì)和組織結(jié)構(gòu).很多研究表明,復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)特征不同于網(wǎng)絡(luò)的全局結(jié)構(gòu)特征[2].因此,復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分一直是重要的研究領(lǐng)域.近年來(lái),很多研究者從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)屬性等各種特性上研究社團(tuán)劃分的方法.由于復(fù)雜網(wǎng)絡(luò)具有結(jié)構(gòu)稀疏、節(jié)點(diǎn)度分布呈現(xiàn)冪率分布和長(zhǎng)尾分布等特性,基于拓?fù)浣Y(jié)構(gòu)的社團(tuán)劃分算法在實(shí)際復(fù)雜網(wǎng)絡(luò)中的劃分效果并不理想.聚類(lèi)技術(shù)也可以應(yīng)用于社團(tuán)劃分,聚類(lèi)可以利用節(jié)點(diǎn)的結(jié)構(gòu)特性、描述屬性等,使用聚類(lèi)結(jié)果作為社團(tuán)劃分的依據(jù).聚類(lèi)方法一般需要對(duì)節(jié)點(diǎn)表示成一個(gè)稀疏的高維向量,高維稀疏向量不僅難以有效地表達(dá)結(jié)構(gòu)的上下文結(jié)構(gòu)信息,而且高維聚類(lèi)算法復(fù)雜度也較高.

深度學(xué)習(xí)被廣泛應(yīng)用于機(jī)器學(xué)習(xí)、自然語(yǔ)言處理中.Word2Vec巧妙地利用了詞的上下文結(jié)構(gòu),采用三層神經(jīng)網(wǎng)絡(luò)對(duì)詞構(gòu)造分布式向量表達(dá).自從詞向量提出后,很多研究者對(duì)不同的研究對(duì)象進(jìn)行了向量化.用低維的實(shí)向量表達(dá)一個(gè)對(duì)象具有維度低、包含上下文信息等優(yōu)點(diǎn),所以得到了很多研究者的關(guān)注.文獻(xiàn)[3]分析了復(fù)雜網(wǎng)絡(luò)中隨機(jī)游走產(chǎn)生的節(jié)點(diǎn)序列的頻率,發(fā)現(xiàn)其和文本分析中的詞一樣具有長(zhǎng)尾效應(yīng),滿足zipf定律,首次提出一種網(wǎng)絡(luò)節(jié)點(diǎn)的向量表示方法,并在標(biāo)簽預(yù)測(cè)上進(jìn)行了應(yīng)用實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,節(jié)點(diǎn)向量能夠表示節(jié)點(diǎn)所在的結(jié)構(gòu)特性,所以在標(biāo)簽預(yù)測(cè)上效果較好.

受其啟發(fā),本文將分布式節(jié)點(diǎn)向量表達(dá)和聚類(lèi)方法相結(jié)合應(yīng)用于復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分[4,5],在利用分布式節(jié)點(diǎn)向量進(jìn)行社團(tuán)劃分時(shí),期望節(jié)點(diǎn)的上下文能夠較好地刻畫(huà)社團(tuán)內(nèi)部和外部的差異,所以本文提出一個(gè)啟發(fā)式隨機(jī)游走模型,將啟發(fā)式隨機(jī)游走的路徑作為節(jié)點(diǎn)上下文,采用分層回歸(hierarchical softmax)方法生成節(jié)點(diǎn)向量,利用節(jié)點(diǎn)向量進(jìn)行快速聚類(lèi),實(shí)現(xiàn)社團(tuán)劃分.

2 研究現(xiàn)狀

近年來(lái),復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分研究受到國(guó)內(nèi)外研究者的大量關(guān)注,他們提出了不同類(lèi)型的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分方法,主要可以分為以下3類(lèi).

(1) 基于優(yōu)化的劃分方法,其代表是譜方法和聚類(lèi)方法.譜方法[6,7]可以用來(lái)進(jìn)行社團(tuán)劃分,其原理是由網(wǎng)絡(luò)鄰接矩陣的特征值和其對(duì)應(yīng)特征向量來(lái)劃分網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu).付立東等人[8]基于核矩陣的最大特征向量和特征值提出了模塊密度中心性,用來(lái)度量節(jié)點(diǎn)對(duì)不同社團(tuán)的貢獻(xiàn)度,在此基礎(chǔ)上劃分社團(tuán).Riolo等人[9]為了能夠使網(wǎng)絡(luò)的最小分割矩陣映射到譜中,對(duì)網(wǎng)絡(luò)的最小分割矩陣進(jìn)行了優(yōu)化.然而,譜方法在網(wǎng)絡(luò)中社團(tuán)的數(shù)量識(shí)別方面存在著明顯的缺陷,因?yàn)橥ㄟ^(guò)遞歸二分策略得到的劃分結(jié)果不一定是最優(yōu)解.Liu等人[10]將節(jié)點(diǎn)的中心度和節(jié)點(diǎn)間的吸引力分別作為節(jié)點(diǎn)和連邊的權(quán)重,在聚類(lèi)時(shí)保證每個(gè)簇內(nèi)節(jié)點(diǎn)的權(quán)重之和與簇和簇之間節(jié)點(diǎn)連邊權(quán)重之和的差值最大,在此基礎(chǔ)上提出了基于節(jié)點(diǎn)中心性和節(jié)點(diǎn)間吸引力的加權(quán)節(jié)點(diǎn)聚類(lèi)算法.Wang等人[11]利用網(wǎng)絡(luò)的潛在拓?fù)浣Y(jié)構(gòu)的拉普拉斯矩陣提出了基于網(wǎng)絡(luò)潛在拓?fù)浣Y(jié)構(gòu)的譜聚類(lèi)算法,該算法充分利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息,并且利用局部最大潛在節(jié)點(diǎn)對(duì)劃分的最終社團(tuán)數(shù)目進(jìn)行優(yōu)化.Jin等人[12]利用物理拓?fù)渚嚯x度量聚類(lèi)時(shí)簇的距離,在此基礎(chǔ)上提出了基于密度的社團(tuán)劃分方法.Lin等人[13]發(fā)現(xiàn)在網(wǎng)絡(luò)的結(jié)構(gòu)信息不完整時(shí),可以通過(guò)已知局部區(qū)域的邊信息來(lái)度量網(wǎng)絡(luò)(缺失部分邊的條件下)中節(jié)點(diǎn)間的距離,并進(jìn)一步利用層次聚類(lèi)劃分網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu).Gennip等人[14]將譜聚類(lèi)算法應(yīng)用于地理定位數(shù)據(jù)中的社團(tuán)發(fā)現(xiàn),并對(duì)不同地理信息編碼方式對(duì)最終劃分結(jié)果的影響進(jìn)行了探索.Kernighan等人[15]基于貪婪思想提出了一種試探優(yōu)化社團(tuán)劃分算法.Newman快速算法[16]通過(guò)不停地在網(wǎng)絡(luò)中添加邊來(lái)快速、有效地對(duì)大型網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分.Ying等人[17]提出通過(guò)迭代的方式把每個(gè)節(jié)點(diǎn)劃分到與其擁有最大相似度的社團(tuán)來(lái)發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu).Zanjani等人[18]從節(jié)點(diǎn)間的連接關(guān)系的緊密程度和依賴關(guān)系的強(qiáng)弱程度來(lái)判斷節(jié)點(diǎn)間的關(guān)系,將關(guān)系緊密的節(jié)點(diǎn)劃分到同一個(gè)社團(tuán)中,進(jìn)一步對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分.王興元等人[19]利用節(jié)點(diǎn)間依賴度進(jìn)行社團(tuán)劃分.Clauset等人[20]基于R值提出了局部社團(tuán)發(fā)現(xiàn)算法,R為局部模塊度,然后基于貪心算法的思想迭代地添加鄰居節(jié)點(diǎn),在此過(guò)程中,要求R值增加最大化.Lancichinetti等人[21]基于社團(tuán)局部結(jié)構(gòu)定義一個(gè)適應(yīng)度函數(shù),在此基礎(chǔ)上提出了基于適應(yīng)度函數(shù)的重疊社團(tuán)劃分算法(LFM).針對(duì) LFM 算法隨機(jī)選擇初始種子節(jié)點(diǎn),可能存在算法陷入死循環(huán)的問(wèn)題,Lee等人[22]選擇極大子圖 clique作為初始社團(tuán)取代 LFM 算法中種子節(jié)點(diǎn)隨機(jī)選擇策略,在此基礎(chǔ)上提出GCE算法.此類(lèi)算法需要社團(tuán)數(shù)量或社團(tuán)的平均規(guī)模大小等先驗(yàn)知識(shí),并且對(duì)初值的選取比較敏感,若初值的選取策略不當(dāng)可能會(huì)導(dǎo)致算法不易收斂,結(jié)果較差；Newman快速算法等基于貪心算法思想的方法,在推廣至大規(guī)模社團(tuán)劃分場(chǎng)景時(shí),存在收斂速度慢、時(shí)間復(fù)雜度較高等問(wèn)題.Xu等人[23]將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為社區(qū)節(jié)點(diǎn)、樞紐節(jié)點(diǎn)和邊緣節(jié)點(diǎn)這 3類(lèi)節(jié)點(diǎn),提出了 SCAN算法用于對(duì) 3類(lèi)節(jié)點(diǎn)的聚類(lèi)分析.Huang等人[24]提出了一種SHRINK 模型,該模型在樞紐節(jié)點(diǎn)及邊緣節(jié)點(diǎn)的基礎(chǔ)上,加入了社團(tuán)的層級(jí)結(jié)構(gòu)信息,在真實(shí)數(shù)據(jù)集上取得了很多好的劃分結(jié)果.

(2) 啟發(fā)式劃分方法,主要是基于網(wǎng)絡(luò)結(jié)構(gòu)的社團(tuán)劃分算法.GN(Girvan-Newman)算法[25]的提出對(duì)社團(tuán)劃分研究的發(fā)展有著重要意義,Girvan和 Newman創(chuàng)新性地提出了“邊介數(shù)”,邊介數(shù)較高的邊更有可能是社團(tuán)之間的連邊,刪除這些邊介數(shù)高的邊可以很好地劃分社團(tuán).GN算法的精確度有了顯著的提高,然而其時(shí)間復(fù)雜度卻非常高.Vincent等人[26]基于模塊度優(yōu)化提出了一種啟發(fā)式社團(tuán)劃分算法Fast Unfoliding.算法包括兩個(gè)步驟:首先將每個(gè)節(jié)點(diǎn)分配到指定的社團(tuán),然后在社團(tuán)間按序移動(dòng)分配好的節(jié)點(diǎn)；然后將上一階段得到的社團(tuán)作為新的“節(jié)點(diǎn)”,重新構(gòu)造新的子圖.Raghavan等人[27]基于標(biāo)簽傳播算法(LPA)進(jìn)行社團(tuán)劃分,LPA為每個(gè)節(jié)點(diǎn)指定一個(gè)標(biāo)簽,然后迭代更新節(jié)點(diǎn)的標(biāo)簽,直到所有節(jié)點(diǎn)達(dá)到收斂為止.Sun等人[28]提出了一種基于中心的標(biāo)簽傳播算法 CenLP,該方法主要通過(guò)計(jì)算本地密度和節(jié)點(diǎn)與高密度節(jié)點(diǎn)的相似性來(lái)改進(jìn)標(biāo)簽傳播算法,該方法基本不需要人工設(shè)置參數(shù),就可以適用于較大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù).Tsourakakis等人[29]在兩種正交的啟發(fā)式搜索算法的基礎(chǔ)上提出一個(gè)框架,其中,這兩種啟發(fā)式算法可以通過(guò)權(quán)值來(lái)進(jìn)行量化,這個(gè)框架能夠應(yīng)用到傳統(tǒng)的社團(tuán)劃分算法中,使它們的性能得到提高.袁超等人[30]提出了節(jié)點(diǎn)相似度模型應(yīng)用于局部社團(tuán)挖掘,進(jìn)一步使用“內(nèi)外夾逼”的思想,提出了一種有效的社團(tuán)發(fā)現(xiàn)算法(SICE).這類(lèi)算法的共同特點(diǎn)是它們都是基于某些直觀的假設(shè)來(lái)設(shè)計(jì)啟發(fā)式算法,對(duì)于大部分網(wǎng)絡(luò)來(lái)說(shuō),它們能夠快速尋得最優(yōu)解或近似解,但無(wú)法從理論上保證算法對(duì)具有任何結(jié)構(gòu)的輸入網(wǎng)絡(luò)都能找到最優(yōu)或近似最優(yōu)解.

(3) 其他劃分方法.Albert等人[31]利用雙曲率對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行有限的描述,可以很好地發(fā)現(xiàn)網(wǎng)絡(luò)中的一些具有高階連通性的節(jié)點(diǎn),并將這些節(jié)點(diǎn)作為社團(tuán)發(fā)現(xiàn)的重要節(jié)點(diǎn).淦文燕等人[32]基于拓?fù)鋭?shì)提出了一種新的社團(tuán)劃分算法,算法將拓?fù)鋭?shì)場(chǎng)的局部高勢(shì)區(qū)看成社團(tuán),并且連通的高勢(shì)區(qū)被低勢(shì)區(qū)所分割,利用網(wǎng)絡(luò)的這些高勢(shì)區(qū)可以發(fā)現(xiàn)網(wǎng)絡(luò)中的社團(tuán).Wu等人[33]將復(fù)雜網(wǎng)絡(luò)類(lèi)比為電路系統(tǒng),網(wǎng)絡(luò)中的邊類(lèi)比為電阻,邊連接的節(jié)點(diǎn)之間存在電勢(shì)差,在此基礎(chǔ)上提出了快速啟發(fā)式社團(tuán)發(fā)現(xiàn)算法(WH).何東曉等人[34]基于聚類(lèi)融合提出了一種遺傳算法,并將其應(yīng)用于社區(qū)發(fā)現(xiàn),遺傳算法利用父節(jié)點(diǎn)的聚類(lèi)信息結(jié)合網(wǎng)絡(luò)的局部拓?fù)浣Y(jié)構(gòu)信息,產(chǎn)生新節(jié)點(diǎn).Okamoto等人[35]提出將復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)視為神經(jīng)網(wǎng)絡(luò)中的細(xì)胞集合進(jìn)行社團(tuán)劃分.張忠元等人[36]在網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)問(wèn)題中引入字典學(xué)習(xí)算法形成新的算法,該算法結(jié)合了字典學(xué)習(xí)算法和最小二乘方回歸,算法更加簡(jiǎn)單,收斂速度更快,且在社團(tuán)發(fā)現(xiàn)中取得了較好的效果.除了將物理、生物等自然科學(xué)學(xué)科知識(shí)引入復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分外,有研究者嘗試將復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)或邊進(jìn)行向量化表示,利用得到的節(jié)點(diǎn)或邊向量進(jìn)行社團(tuán)劃分.Tang等人[37]基于社交網(wǎng)絡(luò)中人與人之間的交互行為,提出將節(jié)點(diǎn)作為邊的特征對(duì)邊進(jìn)行向量化表示,這種邊緣-中心算法能夠處理稀疏網(wǎng)絡(luò)并具有可擴(kuò)展性等特點(diǎn).

基于優(yōu)化的劃分方法和啟發(fā)式劃分方法存在各自的缺陷,如何利用節(jié)點(diǎn)的結(jié)構(gòu)特性,構(gòu)造具有良好性能的社團(tuán)劃分算法是本文研究的目標(biāo).本文將自然語(yǔ)言處理(NLP)中的語(yǔ)言模型應(yīng)用于復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)特征向量的學(xué)習(xí),節(jié)點(diǎn)的特征向量在一定程度上可以反映復(fù)雜網(wǎng)絡(luò)中的信息,最后通過(guò)聚類(lèi)的方法完成網(wǎng)絡(luò)中節(jié)點(diǎn)所屬社團(tuán)的識(shí)別.近年來(lái),隨著深度學(xué)習(xí)的發(fā)展,也產(chǎn)生了很多新的節(jié)點(diǎn)表示學(xué)習(xí)方法,如基于隨機(jī)游走的模型DeepWalk、node2vec,基于近鄰相似性的 LINE[38]、GraRep[39]、SDNE[40],引入其他屬性、文本信息[41,42]的 TADW[43]、GENE[44]等,這些方法雖然不同程度地包含了網(wǎng)絡(luò)的結(jié)構(gòu)、屬性、文本等信息,但目前針對(duì)社團(tuán)劃分任務(wù)的網(wǎng)絡(luò)表示方法仍有待研究.

3 基于節(jié)點(diǎn)向量表達(dá)的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法

本文提出一種基于節(jié)點(diǎn)向量表達(dá)的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法(community detection algorithm based on node embedding vector,簡(jiǎn)稱CDNEV).

CDNEV算法主要包含 3個(gè)步驟,為了對(duì)節(jié)點(diǎn)生成分布式向量表達(dá),首先需要構(gòu)造包含節(jié)點(diǎn)上下文的語(yǔ)料庫(kù).節(jié)點(diǎn)上下文語(yǔ)料庫(kù)對(duì)社團(tuán)劃分具有重要作用,為了克服隨機(jī)游走算法帶來(lái)的節(jié)點(diǎn)上下文不能很好地刻畫(huà)社團(tuán)結(jié)構(gòu)的特性,我們提出一種啟發(fā)式隨機(jī)游走算法,對(duì)每個(gè)節(jié)點(diǎn)生成固定長(zhǎng)度的上下文節(jié)點(diǎn)序列,作為語(yǔ)料庫(kù)；然后利用SkipGram模型來(lái)生成分布式節(jié)點(diǎn)表示向量；最后利用特征向量進(jìn)行聚類(lèi),得到復(fù)雜網(wǎng)絡(luò)中社團(tuán)劃分的結(jié)果.下文將使用的數(shù)學(xué)符號(hào)列于表1中.

Table 1 Main symbols表1 主要符號(hào)列表

3.1 啟發(fā)式隨機(jī)游走

在語(yǔ)言模型中,詞是處理的基本對(duì)象,句子是詞的上下文載體,句子集構(gòu)成語(yǔ)料庫(kù).在復(fù)雜網(wǎng)絡(luò)上,節(jié)點(diǎn)是處理的基本對(duì)象,但沒(méi)有承載節(jié)點(diǎn)的句子,文獻(xiàn)[3]中采用了隨機(jī)游走生成節(jié)點(diǎn)的上下文節(jié)點(diǎn)序列,這樣構(gòu)造出由節(jié)點(diǎn)序列形成的“句子”,在節(jié)點(diǎn)上進(jìn)行不同的隨機(jī)游走可以得到不同的句子,形成語(yǔ)料庫(kù).

隨機(jī)游走具有不確定性.一般地,自然語(yǔ)言中的句子是滿足特定語(yǔ)法規(guī)則和含義的詞串,若采用完全隨機(jī)游走的方式把復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)序列轉(zhuǎn)化為句子,容易產(chǎn)生許多隨機(jī)性很強(qiáng)的句子,這些句子相當(dāng)于自然語(yǔ)言中的不符合語(yǔ)法或噪聲很大的句子,對(duì)語(yǔ)言模型訓(xùn)練出來(lái)的詞向量(節(jié)點(diǎn)的特征向量)會(huì)帶來(lái)負(fù)面效果.因此,我們提出一種啟發(fā)式隨機(jī)游走算法,首先通過(guò)隨機(jī)游走生成加權(quán)的k-step圖,然后在k-step圖上進(jìn)行概率隨機(jī)游走,提高生成節(jié)點(diǎn)序列的社團(tuán)合理性.

3.1.1 啟發(fā)式隨機(jī)游走相關(guān)定義

在語(yǔ)言模型中,隨機(jī)游走過(guò)程主要表示為:網(wǎng)絡(luò)上的任意一個(gè)節(jié)點(diǎn)依照某一概率,從當(dāng)前位置轉(zhuǎn)移到與其有邊連接的鄰居節(jié)點(diǎn)的過(guò)程.令G表示一個(gè)給定節(jié)點(diǎn)數(shù)為n的加權(quán)復(fù)雜網(wǎng)絡(luò),其鄰接矩陣為A=|aij|n×n,aij,表示節(jié)點(diǎn)i和j的連接布爾值.邊權(quán)w(eij)表示節(jié)點(diǎn)i和j連邊的權(quán)重,將其初始化為1.

復(fù)雜網(wǎng)絡(luò)中相距較遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的交互行為一般較少,相互影響較弱.啟發(fā)式隨機(jī)游走算法中相關(guān)定義如下.

定義1(k-step).k-step表示在圖G中進(jìn)行隨機(jī)游走,當(dāng)步長(zhǎng)為k或遇到預(yù)設(shè)停止條件時(shí),結(jié)束當(dāng)次隨機(jī)游走,其中,0

定義2(k-step概率).令e∈E表示圖G的一條邊,k-step概率Pk(e)表示從當(dāng)前節(jié)點(diǎn)進(jìn)行隨機(jī)游走過(guò)程選擇通過(guò)邊e的概率.

定義3(預(yù)處理k-step圖).預(yù)處理k-step圖是圖G中每個(gè)節(jié)點(diǎn)通過(guò)m次步長(zhǎng)為k的完全隨機(jī)游走生成的加權(quán)圖,其中,完全隨機(jī)游走指的是當(dāng)前節(jié)點(diǎn)所對(duì)應(yīng)的每一條邊的k-step概率的值相同,邊的權(quán)重為該邊在完全隨機(jī)游走過(guò)程中被遍歷的次數(shù).

生成預(yù)處理k-step圖的基本過(guò)程如下:令當(dāng)前節(jié)點(diǎn)所對(duì)應(yīng)的每一條邊的k-step概率為相同值,即以等概率選擇任意一條邊作為下一步.每經(jīng)過(guò)一條邊就將該點(diǎn)對(duì)應(yīng)的w(eij)加1,循環(huán)m次游走過(guò)程.

因?yàn)閺?fù)雜網(wǎng)絡(luò)社區(qū)具有“內(nèi)緊外松”的特性,所以,社區(qū)內(nèi)節(jié)點(diǎn)間的交互行為比社區(qū)之間的聯(lián)系更為頻繁.預(yù)處理k-step圖中的完全隨機(jī)游走過(guò)程中經(jīng)過(guò)社團(tuán)內(nèi)部的次數(shù)應(yīng)該明顯多于經(jīng)過(guò)社團(tuán)間的次數(shù).由此可得:經(jīng)過(guò)預(yù)處理的k-step圖中每一個(gè)節(jié)點(diǎn)與其鄰節(jié)點(diǎn)所形成的連邊中,邊的權(quán)值越大,其對(duì)應(yīng)的k-step概率越大,最終在生成節(jié)點(diǎn)序列的啟發(fā)隨機(jī)游走的過(guò)程中,從當(dāng)前節(jié)點(diǎn)經(jīng)過(guò)該邊的概率越大,從而形成對(duì)社區(qū)劃分更合理的“句子”.

3.1.2 啟發(fā)式隨機(jī)游走算法

算法1.RandomWalkByWeight (G,vi,k).

根據(jù)第3.1.1節(jié)所述,可以將算法分為生成預(yù)處理k-step圖和k-step啟發(fā)式隨機(jī)游走兩個(gè)部分.生成預(yù)處理k-step圖的流程如下.

Step 1:把復(fù)雜網(wǎng)絡(luò)的每一條邊的權(quán)值w(eij)初始化為1.

Step 2:將圖中的每一個(gè)節(jié)點(diǎn)依次作為源節(jié)點(diǎn)進(jìn)行完全隨機(jī)游走.完全隨機(jī)游走即從當(dāng)前節(jié)點(diǎn)出發(fā),對(duì)于所有鄰邊將其作為一條路徑的概率均相等.完全隨機(jī)游走過(guò)程有k步,每經(jīng)過(guò)一條邊就將該點(diǎn)對(duì)應(yīng)的w(eij)加1.

Step 3:重復(fù)m次Step 2,生成經(jīng)過(guò)預(yù)處理的k-step圖,即得到該網(wǎng)絡(luò)預(yù)處理后的最終邊權(quán),易知,某一條邊的權(quán)值越大,這條邊對(duì)識(shí)別社團(tuán)的貢獻(xiàn)越大.

綜上所述,假設(shè)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為n,隨機(jī)游走長(zhǎng)度為k,迭代網(wǎng)絡(luò)次數(shù)為M,那么生成預(yù)處理k-step圖的時(shí)間復(fù)雜度為O(Mkn).

k-step啟發(fā)式隨機(jī)游走是在圖G上利用預(yù)處理k-step圖生成的權(quán)重進(jìn)行加權(quán)隨機(jī)游走,具體算法如算法1所示.算法包含4個(gè)主要步驟.

Step 1:對(duì)生成的預(yù)處理k-step圖中每個(gè)節(jié)點(diǎn)與相連的邊進(jìn)行歸一化處理,把與一個(gè)節(jié)點(diǎn)相連的所有邊的權(quán)值轉(zhuǎn)化為相應(yīng)的概率(line 1,算法1).設(shè)節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的連邊被選中的概率為

Step 2:選取指定節(jié)點(diǎn)作為源節(jié)點(diǎn)進(jìn)行k-step隨機(jī)游走,k-step過(guò)程根據(jù)Step 1計(jì)算當(dāng)前節(jié)點(diǎn)到其鄰節(jié)點(diǎn)的選擇概率,依概率分布選擇下一跳的節(jié)點(diǎn),經(jīng)過(guò)k步后得到一條長(zhǎng)度為k的路徑(line 2～line 5,算法1).

Step 3:檢驗(yàn)生成路徑里包含的不同節(jié)點(diǎn)的數(shù)量,若不同節(jié)點(diǎn)的數(shù)量少于,則放棄這一條路徑(line 6～line 8,算法 1).

Step 4:返回長(zhǎng)度為k的節(jié)點(diǎn)序列用于語(yǔ)言模型生成節(jié)點(diǎn)的特征向量.

綜上所述,假設(shè)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)為n,隨機(jī)步長(zhǎng)為k,那么k-step啟發(fā)式隨機(jī)游走的時(shí)間復(fù)雜度為O(kn)；若需要生成的隨機(jī)游走序列數(shù)量為m,那么時(shí)間復(fù)雜度為O(mkn).通常M＜＜m,且m為常數(shù),則 RandomWalkBy Weight算法的時(shí)間復(fù)雜度為O(mkn).

當(dāng)網(wǎng)絡(luò)存在局部特殊拓?fù)浣Y(jié)構(gòu),例如孤立連接或者孤立回路等極端情況時(shí),k-step隨機(jī)游走過(guò)程會(huì)重復(fù)遍歷相同的節(jié)點(diǎn)或形成局部回路,使路徑中的節(jié)點(diǎn)重復(fù)率很高.因此,我們給隨機(jī)游走路徑中節(jié)點(diǎn)重復(fù)率設(shè)定一個(gè)閾值,若一條路徑中不同節(jié)點(diǎn)的數(shù)量少于,則放棄生成的這條路徑.k-step隨機(jī)游走過(guò)程中步長(zhǎng)k的設(shè)定是至關(guān)重要的,過(guò)大的k值容易使隨機(jī)游走過(guò)程陷入“重復(fù)陷阱”,提高了路徑的棄用率并增加了算法的時(shí)間復(fù)雜度；過(guò)小的k值不能保證隨機(jī)游走的覆蓋效果.本文基于網(wǎng)絡(luò)中社團(tuán)平均直徑較小的事實(shí),通過(guò)在不同規(guī)模已知且有標(biāo)記的網(wǎng)絡(luò)上利用網(wǎng)格計(jì)算,得出k的經(jīng)驗(yàn)最優(yōu)值區(qū)間為[23,45].

3.2 分布式節(jié)點(diǎn)表達(dá)向量生成

3.2.1 統(tǒng)計(jì)語(yǔ)言模型

統(tǒng)計(jì)語(yǔ)言模型的目標(biāo)是計(jì)算一個(gè)特定序列的詞在語(yǔ)料庫(kù)中出現(xiàn)的概率,假設(shè)Wn=(w1,w2,…,wn)是由n個(gè)詞w1,w2,…,wn按順序構(gòu)成的一個(gè)句子,則句子的概率為詞的聯(lián)合概率 Pr(s)=Pr(w1,…,wn-1,wn),利用貝葉斯公式可以將其分解為

其中,Contexti表示wi的上下文,P r(w1) Pr(w1|w2) ...Pr(wn|w1,...,wn-1)就是統(tǒng)計(jì)語(yǔ)言模型的參數(shù).

在統(tǒng)計(jì)語(yǔ)言模型中,假設(shè)語(yǔ)料庫(kù)對(duì)應(yīng)的字典的大小為N,一個(gè)給定長(zhǎng)度為L(zhǎng)的句子,需要計(jì)算L個(gè)參數(shù),考慮長(zhǎng)度為L(zhǎng)的任意句子有NL種可能,而每種需要計(jì)算L個(gè)參數(shù),通過(guò)計(jì)算MNL個(gè)參數(shù),計(jì)算量巨大且存儲(chǔ)這些信息內(nèi)存開(kāi)銷(xiāo)也很大.為了快速計(jì)算模型參數(shù),學(xué)術(shù)界提出多種模型,如N-gram模型、N-pos模型和神經(jīng)網(wǎng)絡(luò)等方法.Bengio等人[46]提出了一種基于詞向量的神經(jīng)概率語(yǔ)言模型.神經(jīng)網(wǎng)絡(luò)語(yǔ)言模型可以簡(jiǎn)單地歸納為:(1) 將單詞映射到m維特征空間中；(2) 使用單詞序列的對(duì)應(yīng)向量集合作為輸入表達(dá)單詞序列的聯(lián)合概率方程；(3) 同步學(xué)習(xí)單詞的特征向量和概率函數(shù).本文借助神經(jīng)網(wǎng)絡(luò)概率語(yǔ)言模型的思想,通過(guò)將整個(gè)復(fù)雜網(wǎng)絡(luò)類(lèi)比為語(yǔ)料庫(kù),復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)相當(dāng)于語(yǔ)料庫(kù)中的詞,使用啟發(fā)式隨機(jī)游走生成節(jié)點(diǎn)序列Wv=(v1,v2,…,vi),節(jié)點(diǎn)序列把類(lèi)比為統(tǒng)計(jì)語(yǔ)言模型中的詞序列,對(duì)應(yīng)的參數(shù)為Pr(v1)Pr(v1|v2)…Pr(vn|v1,…,vn-1),即目標(biāo)函數(shù)為

我們希望得到一個(gè)能夠表示節(jié)點(diǎn)間關(guān)系的特征向量,因此將要學(xué)習(xí)獲得的各節(jié)點(diǎn)的向量表示為

Φ表示了復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)之間潛在的相互關(guān)系,即節(jié)點(diǎn)的特征向量.目標(biāo)函數(shù)由式(1)變?yōu)?/p>

易知,隨著隨機(jī)游走長(zhǎng)度k的增加,條件概率式(2)的分母有!種情況,因此計(jì)算量將非常巨大.

3.2.2 SkipGram模型

為了應(yīng)對(duì)一般統(tǒng)計(jì)語(yǔ)言模型中條件概率計(jì)算量大的問(wèn)題,文獻(xiàn)[47,48]提出了一個(gè)放松的統(tǒng)計(jì)語(yǔ)言模型SkipGram,該模型采用wi預(yù)測(cè)其上下文wi-1,wi-2,wi+1,wi+2的概率,類(lèi)似于N-gram 模型規(guī)定了定長(zhǎng)的“詞語(yǔ)窗口”,wi的上下文僅由“詞語(yǔ)窗口”內(nèi)的詞組成而不是整個(gè)句子；并且它不受“詞語(yǔ)窗口”內(nèi)的詞序的約束,只需最大化地給定wi,不考慮“詞語(yǔ)窗口”內(nèi)詞序的條件概率,不考慮任何其他先驗(yàn)知識(shí).利用放松的統(tǒng)計(jì)語(yǔ)言模型方法,新的目標(biāo)函數(shù)為

SkipGram不考慮“詞語(yǔ)窗口”內(nèi)的詞序的假設(shè),對(duì)于復(fù)雜網(wǎng)絡(luò)上的節(jié)點(diǎn)游走序列而言,節(jié)點(diǎn)的次序并不重要,所以,SkipGram 適合節(jié)點(diǎn)特征向量的學(xué)習(xí).直觀分析,網(wǎng)絡(luò)游走序列相似的節(jié)點(diǎn)擁有相似的拓?fù)浣Y(jié)構(gòu)特征,也就是網(wǎng)絡(luò)游走序列相似的節(jié)點(diǎn)的特征向量應(yīng)該相似,所以,可以通過(guò)優(yōu)化目標(biāo)函數(shù)式(3)得到節(jié)點(diǎn)的特征向量.

SkipGram模型假設(shè)式(3)中的條件概率之間相互獨(dú)立,得到:

SkipGram模型的參數(shù)求解算法如算法2所示,算法2中節(jié)點(diǎn)v表示為 Φ (v)∈ ?d,迭代遍歷了節(jié)點(diǎn)序列中所有節(jié)點(diǎn)的窗口(line 1～line 2,算法2).在給定節(jié)點(diǎn)vj的情況下,最大化其節(jié)點(diǎn)序列中鄰居節(jié)點(diǎn)的條件概率(line 3,算法2),并據(jù)此更新節(jié)點(diǎn)向量的表示.算法2中有條件概率Pr(Φ(uk)|Φ(vj)),在神經(jīng)概率語(yǔ)言模型中條件概率最樸素的形式為,其中,為神經(jīng)網(wǎng)絡(luò)中常用的能量函數(shù).易知,最里層的循環(huán)后驗(yàn)概率分母的計(jì)算量為O(|V|×d),計(jì)算量非常大,該過(guò)程稱為 softmax歸一化處理.為了提升算法效率,我們引入Hierarchical Softmax方法來(lái)計(jì)算后驗(yàn)概率.

3.2.3 Hierarchical Softmax方法

由第 3.2.2節(jié)可知,計(jì)算 Pr(Φ(uk)|Φ(vj))的計(jì)算量非常大,主要是因?yàn)?softmax歸一化處理需要計(jì)算,因此,使用Hierarchical Softmax[49,50]方法來(lái)解決這一問(wèn)題.另外,采用Hierarchical Softmax方法還能保證參數(shù)學(xué)習(xí)過(guò)程可以較快地收斂.

假設(shè)復(fù)雜網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)于 Huffman樹(shù)的一個(gè)葉子節(jié)點(diǎn),將原來(lái)考慮整個(gè)復(fù)雜網(wǎng)絡(luò)中所有節(jié)點(diǎn)的線性概率最大化問(wèn)題轉(zhuǎn)化為Huffman樹(shù)由根節(jié)點(diǎn)到某一葉子節(jié)點(diǎn)的概率最大化問(wèn)題,Huffman樹(shù)由啟發(fā)式隨機(jī)游走生成的節(jié)點(diǎn)序列中各節(jié)點(diǎn)出現(xiàn)的頻率生成.假設(shè)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)uk為 Huffman樹(shù)中的一個(gè)葉子節(jié)點(diǎn),從Huffman樹(shù)的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)uk所有的非葉子節(jié)點(diǎn)為,其中,b0為根節(jié)點(diǎn),為uk,得到:

通過(guò)引入 Huffman樹(shù)表示Pr(Φ(uk)|Φ(vj)),將其轉(zhuǎn)化成「log|V|」個(gè)二分類(lèi),二分類(lèi)函數(shù)使用logistic分類(lèi)函數(shù),得到:

其中,bl為非葉子節(jié)點(diǎn),Φ(bl)∈ ?d即非葉子節(jié)點(diǎn)的向量映射函數(shù),φ(bl)為類(lèi)別向量.通過(guò)Hierarchical Softmax方法,我們將計(jì)算 Pr(Φ(uk)|Φ(vj))的時(shí)間復(fù)雜度由O(|V|)降低為O(「log|V|」).

算法2.SkipGram (Φ,Wvi,w).

3.2.4 訓(xùn)練模型參數(shù)

語(yǔ)言模型中的參數(shù)θ={Φ,φ},每一個(gè)參數(shù)的規(guī)模為?d,參數(shù)可以通過(guò)隨機(jī)梯度下降(SGD)[51]進(jìn)行參數(shù)的學(xué)習(xí).為了使用SGD,需要求出參數(shù)的梯度.將公式(6)寫(xiě)成整體的形式,有:

將式(7)代入式(5),再將式(5)代入式(4),對(duì)式(4)求對(duì)數(shù)似然可得:

令:

分別對(duì)式(9)求關(guān)于Φ(vj)和的偏導(dǎo)數(shù),得到式(10).

由式(10)通過(guò)梯度下降法可得:

3.3 聚類(lèi)算法

由于K-Means算法具有運(yùn)行速度快、結(jié)構(gòu)簡(jiǎn)單、可伸縮性等特點(diǎn),所以我們使用K-Means算法對(duì)生成的節(jié)點(diǎn)特征向量進(jìn)行聚類(lèi),得到復(fù)雜網(wǎng)絡(luò)最終的劃分結(jié)果.K-Means聚類(lèi)算法的時(shí)間復(fù)雜度是O(nXt),其中,n表示復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù),t表示算法收斂之前的迭代次數(shù),X表示社團(tuán)數(shù)目.K-Means算法需要給定初始聚類(lèi)中心,我們選擇局部度中心節(jié)點(diǎn)[52]作為K-Means算法的聚類(lèi)中心點(diǎn).具體如算法3所示.

算法 3.K-Means (Φ,k_nodes).

3.4 CDNEV算法整體流程

利用啟發(fā)式隨機(jī)游走算法,對(duì)每個(gè)節(jié)點(diǎn)生成固定長(zhǎng)度的上下文節(jié)點(diǎn)序列,然后利用SkipGram模型生成分布式節(jié)點(diǎn)表示向量,最后利用特征向量進(jìn)行聚類(lèi),得到復(fù)雜網(wǎng)絡(luò)中社團(tuán)劃分的結(jié)果,這是 CDNEV算法的核心過(guò)程,CDNEV算法的具體步驟描述如算法4所示.

算法核心步驟可以分為7步.第 1步,也就是算法第 1行,初始化各節(jié)點(diǎn)向量,得到矩陣,通常情況下,每個(gè)節(jié)點(diǎn)向量的初始化是使用隨機(jī)數(shù)的方法來(lái)實(shí)現(xiàn)；第2步,算法第2行,依據(jù)算法1中完全隨機(jī)游走產(chǎn)生的隨機(jī)節(jié)點(diǎn)序列中節(jié)點(diǎn)的被遍歷頻率創(chuàng)建Huffman樹(shù)；第3步,進(jìn)入啟發(fā)式游走迭代,算法第3行開(kāi)始,算法第4行,生成無(wú)序的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)序列；第4步,從算法的第5行開(kāi)始,對(duì)序列中的每個(gè)節(jié)點(diǎn)進(jìn)行啟發(fā)式隨機(jī)游走,生成長(zhǎng)度為k的節(jié)點(diǎn)序列,算法第6行執(zhí)行；算法第7行,采用SkipGram算法對(duì)每個(gè)節(jié)點(diǎn)向量進(jìn)行優(yōu)化并更新；第5步,算法的第10行,計(jì)算得到每個(gè)節(jié)點(diǎn)的分布式實(shí)向量,其維度采用d表示；第6步,算法的第11行,選擇局部中心度大于網(wǎng)絡(luò)中所有節(jié)點(diǎn)的局部平均中心度,且處于網(wǎng)絡(luò)中前10%的X個(gè)局部度中心節(jié)點(diǎn)作為聚類(lèi)的中心節(jié)點(diǎn)；第7步,算法4的第12行,采用K-Means算法進(jìn)行聚類(lèi),得到社團(tuán)劃分結(jié)果.

算法4.CDNEV (G,w,k,d,r).

4 實(shí)驗(yàn)結(jié)果與分析

我們從優(yōu)化方法和啟發(fā)式方法中選取10種經(jīng)典的社團(tuán)發(fā)現(xiàn)算法進(jìn)行對(duì)比分析和比較,包括GN算法[25]、Newman快速算法(FG)[16]、Leading eigenvector算法(LE)[53]、Infomap算法(IM)[54]、Label propagation算法(LPA)[27]、Spinglass算法(SG)[55]、Walktrap算法(WT)[56]、Louvain算法(LV)[26]、GCE 算法[22]和 LFM 算法[21]和SHRINK算法(SK)[24].

為了更客觀地衡量本文算法的性能,我們也和 DeepWalk(DW)算法[3]、node2vec(N2V)算法進(jìn)行了比較.在用 DeepWalk算法繼續(xù)進(jìn)行社團(tuán)劃分時(shí),我們采取了和本文算法一致的策略,也就是說(shuō),在學(xué)習(xí)到節(jié)點(diǎn)向量的基礎(chǔ)上用K-Means算法進(jìn)行聚類(lèi),從而得到社團(tuán)劃分的結(jié)果.

我們采用社團(tuán)劃分領(lǐng)域常用的測(cè)試數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),數(shù)據(jù)集包括真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和模擬網(wǎng)絡(luò)數(shù)據(jù)集.真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集包括Zachary空手道俱樂(lè)部成員關(guān)系網(wǎng)絡(luò)、寬吻海豚網(wǎng)絡(luò)、美國(guó)政治書(shū)籍網(wǎng)絡(luò)、美國(guó)大學(xué)生橄欖球網(wǎng)絡(luò)、西班牙大學(xué) email通信網(wǎng)絡(luò)和網(wǎng)絡(luò)科學(xué)領(lǐng)域科學(xué)家合作網(wǎng)絡(luò).模擬數(shù)據(jù)集主要由 LFR基準(zhǔn)圖組成,選擇不同的參數(shù)生成不同的LFR基準(zhǔn)圖.

在進(jìn)行實(shí)驗(yàn)時(shí),我們參考了word2vec對(duì)于節(jié)點(diǎn)向量長(zhǎng)度的人為設(shè)定,且針對(duì)大規(guī)模網(wǎng)絡(luò),將節(jié)點(diǎn)嵌入實(shí)向量的維度設(shè)為40.

4.1 算法結(jié)果評(píng)價(jià)指標(biāo)

向量的維度設(shè)為40.在實(shí)驗(yàn)中我們發(fā)現(xiàn),準(zhǔn)確率(precision)、召回率(recall)、F指標(biāo)(F1)和模塊度(modularity)最能刻畫(huà)算法劃分結(jié)果與真實(shí)結(jié)果的差異,為了科學(xué)地衡量不同算法的性能,我們采用上述 4種評(píng)價(jià)指標(biāo)對(duì)不同算法的效果進(jìn)行評(píng)價(jià).

(1) 準(zhǔn)確率(precision,簡(jiǎn)稱P)

準(zhǔn)確率代表社團(tuán)劃分結(jié)果中正確節(jié)點(diǎn)數(shù)量占總節(jié)點(diǎn)數(shù)量的比例,計(jì)算方法為

其中,Lresult表示算法得到的社團(tuán),Lture表示真實(shí)社團(tuán).

(2) 召回率(recall,簡(jiǎn)稱R)

召回率反映了真實(shí)社團(tuán)中被正確劃分出的節(jié)點(diǎn)的比例,計(jì)算方法為

(3)F指標(biāo)(F1)

F1評(píng)價(jià)指標(biāo)是對(duì)P值和R值的綜合,計(jì)算公式為

其中,P為準(zhǔn)確率,R為召回率.

(4) 模塊度(modularity)

模塊度用來(lái)評(píng)價(jià)無(wú)標(biāo)記網(wǎng)絡(luò)中的社團(tuán)劃分結(jié)果,又稱為Q函數(shù).Q函數(shù)為社團(tuán)內(nèi)實(shí)際連接數(shù)目與隨機(jī)連接情況下社團(tuán)內(nèi)期望連接數(shù)目之差,用來(lái)對(duì)網(wǎng)絡(luò)中社團(tuán)的整體質(zhì)量做出一個(gè)定量的評(píng)價(jià).計(jì)算方法如下:

其中,ki和kj表示節(jié)點(diǎn)的度；ci表示節(jié)點(diǎn)i所屬社團(tuán)；m表示網(wǎng)絡(luò)的總邊數(shù).當(dāng)ci=cj時(shí),σ(ci,cj)=1,否則為0.

(5) 標(biāo)準(zhǔn)化互信息(normalized mutual information,簡(jiǎn)稱NMI)

標(biāo)準(zhǔn)化互信息用來(lái)評(píng)價(jià)聚類(lèi)效果.其中,U對(duì)應(yīng)標(biāo)準(zhǔn)結(jié)果,V對(duì)應(yīng)聚類(lèi)的預(yù)測(cè)結(jié)果,計(jì)算方法為

其中,

(6) 調(diào)整蘭德系數(shù)(adjusted rand index,簡(jiǎn)稱ARI)

調(diào)整蘭德系數(shù)用來(lái)評(píng)價(jià)聚類(lèi)結(jié)果的準(zhǔn)確程度,計(jì)算方法為

其中,

其中,a表示標(biāo)準(zhǔn)結(jié)果與預(yù)測(cè)結(jié)果相同的樣本數(shù)量,b表示標(biāo)準(zhǔn)結(jié)果與預(yù)測(cè)結(jié)果不相同的樣本數(shù)量.

4.2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)

實(shí)驗(yàn)采用的真實(shí)網(wǎng)絡(luò)統(tǒng)計(jì)信息見(jiàn)表2.將CDNEV和其他基準(zhǔn)的社團(tuán)劃分算法應(yīng)用于真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集,用每種算法對(duì)不同數(shù)據(jù)集進(jìn)行劃分.對(duì)于有標(biāo)記網(wǎng)絡(luò),因?yàn)槠錁?biāo)注了每個(gè)節(jié)點(diǎn)所屬社團(tuán),所以我們計(jì)算各算法劃分結(jié)果的P、R和F1指標(biāo),并將它們作為定量比較各算法性能的重要依據(jù)；對(duì)于未標(biāo)注網(wǎng)絡(luò),即不確定社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò),因其并沒(méi)有對(duì)每個(gè)節(jié)點(diǎn)歸屬社團(tuán)進(jìn)行標(biāo)注,無(wú)法采用P、R和F1指標(biāo)進(jìn)行比較,本文采用被學(xué)術(shù)界廣泛采用的模塊度對(duì)算法劃分結(jié)果進(jìn)行比較.對(duì)于規(guī)模較小的標(biāo)記網(wǎng)絡(luò),可以人工識(shí)別標(biāo)準(zhǔn)結(jié)果與社團(tuán)劃分結(jié)果的對(duì)應(yīng)關(guān)系,對(duì)于規(guī)模較大的標(biāo)記網(wǎng)絡(luò),則無(wú)法人工識(shí)別此對(duì)應(yīng)關(guān)系,所以,使用 ARI指標(biāo)來(lái)對(duì)社團(tuán)劃分結(jié)果進(jìn)行度量.各算法在真實(shí)網(wǎng)絡(luò)中的劃分結(jié)果見(jiàn)表3.

由表3可知,在Karate網(wǎng)絡(luò)中,CDNEV算法是唯一能夠?qū)⒏鞴?jié)點(diǎn)劃分到其所屬社團(tuán)的算法,在其他有標(biāo)注數(shù)據(jù)集中,CDNEV算法的表現(xiàn)無(wú)論在準(zhǔn)確率、召回率單個(gè)指標(biāo)上,還是在綜合評(píng)價(jià)指標(biāo)F1上,均優(yōu)于對(duì)比算法.我們?cè)?個(gè)數(shù)據(jù)集上,比較了算法的平均指標(biāo).

Table 2 Real networks used in the experiment表2 實(shí)驗(yàn)中用到的真實(shí)網(wǎng)絡(luò)

Table 3 Comparations of CDNEV and baseseline algorithms’ community detection on real networks表3 CDNEV算法與其他算法在真實(shí)網(wǎng)絡(luò)中劃分結(jié)果的比較

F1指標(biāo)值最低的是DW算法,為0.657 5,最高的是LFM算法,為0.851 5,CDNEV算法平均F1則為0.95,明顯高于其他算法.相對(duì)于其他算法,CDNEV算法的F1指標(biāo)平均提高了19%.

在一些特殊情況下,如SG算法和LE算法,在Karate數(shù)據(jù)集上的準(zhǔn)確率也可以達(dá)到100%,但這些算法是將一個(gè)大社團(tuán)中的節(jié)點(diǎn)劃分到多個(gè)子社團(tuán),這種“過(guò)度劃分”導(dǎo)致它們的召回率很低,所以最終的F1值較低.由第3.5節(jié)易知,由于SG算法是基于貪心迭代算法的一種改進(jìn),因此,SG算法相較于CDNEV算法,其時(shí)間復(fù)雜度較高. CDNEV算法與其他算法在E-mail網(wǎng)絡(luò)上的模塊度比較可見(jiàn)表4.

Table 4 Comparations of CDNEV and baseline algorithms’ modularity on E-mail networks表4 CDNEV算法與其他算法在E-mail網(wǎng)絡(luò)上的模塊度比較

DBLP網(wǎng)絡(luò)是標(biāo)記網(wǎng)絡(luò),且網(wǎng)絡(luò)規(guī)模較大,各算法在社團(tuán)劃分上的ARI指標(biāo)見(jiàn)表5,CDNEV算法的ARI指標(biāo)與IM、N2V等算法基本持平,高于其他算法.驗(yàn)證了CDNEV算法在較大規(guī)模網(wǎng)絡(luò)中的可擴(kuò)展性.

Table 5 Comparations of CDNEV and baseline algorithms’ ARI on DBLP networks表5 CDNEV算法與其他算法在DBLP網(wǎng)絡(luò)上的ARI指標(biāo)比較

綜合無(wú)標(biāo)記和有標(biāo)記網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果可知,相較于其他算法,CDNEV算法在真實(shí)網(wǎng)絡(luò)中的劃分效果優(yōu)于其他算法.

4.3 模擬網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)

為了進(jìn)一步評(píng)估這些算法的性能,我們采用LFR[58]人工合成網(wǎng)絡(luò)標(biāo)準(zhǔn)網(wǎng)絡(luò)來(lái)進(jìn)行實(shí)驗(yàn),LFR網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布及社團(tuán)的規(guī)模分布均為冪律分布,使其更接近真實(shí)網(wǎng)絡(luò).本次實(shí)驗(yàn)主要通過(guò)設(shè)置以下參數(shù)來(lái)生成所需的模擬復(fù)雜網(wǎng)絡(luò).

模擬網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)為n；模擬網(wǎng)絡(luò)的節(jié)點(diǎn)平均度為k(P)；模擬網(wǎng)絡(luò)節(jié)點(diǎn)最大度為kmax(Pmax).另外,還需要通過(guò)實(shí)驗(yàn)分析、比較拓?fù)浠旌蠀?shù)μ的作用,μ表示模擬網(wǎng)絡(luò)中社團(tuán)內(nèi)節(jié)點(diǎn)與社團(tuán)外部節(jié)點(diǎn)連接的邊數(shù)占節(jié)點(diǎn)總邊數(shù)的比例,μ越大,說(shuō)明網(wǎng)絡(luò)結(jié)構(gòu)越不明顯；具有指數(shù)分布形式的度分布的參數(shù)ε1,模擬網(wǎng)絡(luò)節(jié)點(diǎn)度分布服從冪指數(shù)為ε1的冪律分布；LFR網(wǎng)絡(luò)的社區(qū)規(guī)模服從指數(shù)分布,其參數(shù)為ε2；最小社區(qū)規(guī)模為cmin,指定最小社區(qū)的節(jié)點(diǎn)數(shù)；最大社區(qū)規(guī)模為cmax,指定最大社區(qū)的節(jié)點(diǎn)數(shù).

按照文獻(xiàn)[59]中的實(shí)驗(yàn)設(shè)計(jì)建議,對(duì)LFR基準(zhǔn)網(wǎng)絡(luò)的參數(shù)設(shè)置如下.

(1) 網(wǎng)絡(luò)規(guī)模n取值為1 000；

(2) 最小社團(tuán)規(guī)模cmin取值為10或20；

(3) 混合參數(shù)μ從0.05變化到0.7,間隔為0.05.

(4) 我們保持其他參數(shù)不變,即節(jié)點(diǎn)的平均度k(P)為 20；最大度kmaxPmax為 2.5倍k(P)；最大社團(tuán)規(guī)模cmax為5倍cmin；節(jié)點(diǎn)度與社團(tuán)規(guī)模的冪律分布指數(shù)分別為ε1=-2,ε2=-1.

我們通過(guò)設(shè)置LFR,模擬不同參數(shù),進(jìn)行了3組實(shí)驗(yàn).

實(shí)驗(yàn)1:設(shè)n=1000,cmin=10,cmax=50,混合參數(shù)μ為變化量,各算法對(duì)應(yīng)的F1值如圖1所示.

實(shí)驗(yàn)2:設(shè)n=1000,cmin=20,cmax=100,混合參數(shù)μ為變化量,各算法對(duì)應(yīng)的F1值如圖2所示.

實(shí)驗(yàn)3:設(shè)μ=0.65,cmin=10,cmax=50,社團(tuán)規(guī)模n為變化量,各算法對(duì)應(yīng)的F1值如圖3所示.

對(duì)實(shí)驗(yàn)1和實(shí)驗(yàn)2,我們生成了2個(gè)網(wǎng)絡(luò)規(guī)模相同、但網(wǎng)絡(luò)結(jié)構(gòu)不同的LFR模擬網(wǎng)絡(luò),通過(guò)分析不同算法隨著混合參數(shù)μ取不同值的劃分效果.為了更進(jìn)一步說(shuō)明 CDNEV算法和其他算法的性能差異,實(shí)驗(yàn)3中我們固定μ=0.65,把網(wǎng)絡(luò)規(guī)模從1 000按間隔為1 000逐步提升到10 000,然后對(duì)比分析不同算法性能隨著網(wǎng)絡(luò)規(guī)模變化的情況.

Fig.1 The variation of different algorithms’F1 with differentμ on base networks, n=1000,cmin=10,cmax=50圖1 不同算法在基準(zhǔn)網(wǎng)絡(luò)上F1值隨μ的變化結(jié)果,n=1000,cmin=10,cmax=50

圖1表示在n=1000,cmin=10,cmax=50；圖2表示在n=1000,cmin=20,cmax=100,分別在混合參數(shù)μ取不同值時(shí),得到對(duì)應(yīng)的F1值.圖1和圖2的2個(gè)子圖是CDNEV和不同算法的比較曲線.圖1和圖2的橫軸表示μ值,縱軸表示F1值.

從圖1和圖2可以看出,在混合參數(shù)μ取值較小時(shí)(μ<0.2),10種算法所表現(xiàn)出來(lái)的F1值差別不明顯,特別是在cmin=20,cmax=100的情況下.但是,隨著混合參數(shù)μ值的增大,網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)開(kāi)始變得模糊化,不同算法之間的性能差異開(kāi)始變大.由圖1和圖2可知,CDNEV對(duì)應(yīng)的F1值一直高于除WT以外的其他算法,并且與WT的差距最多不超過(guò) 0.02.基于隨機(jī)游走的 WT算法的時(shí)間復(fù)雜度主要依賴于網(wǎng)絡(luò)中邊的數(shù)目,時(shí)間復(fù)雜度為O(mn2),而CDNEV的時(shí)間復(fù)雜度僅為O(nlogn),因此本文提出的算法效率遠(yuǎn)高于WT算法.

圖3給出了CDNEV算法和其他算法在不同網(wǎng)絡(luò)規(guī)模下的F1指標(biāo)變化曲線.

Fig.2 The variation of different algorithms’F1 with differentμ on base networks, n=1000,cmin=20,cmax=100圖2 不同算法在基準(zhǔn)網(wǎng)絡(luò)上F1值隨μ的變化結(jié)果,n=1000,cmin=20,cmax=100

Fig.3 The variation of different algorithms’ F1 with different network scales on base networks圖3 不同算法在基準(zhǔn)網(wǎng)絡(luò)規(guī)模變化下的F1值

如圖3所示,可以發(fā)現(xiàn),隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大,不同算法的性能差別同樣逐漸加大.原本在網(wǎng)絡(luò)規(guī)模為1 000時(shí)表現(xiàn)最好的WT算法,隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大,性能逐漸變差.而本文所提出的CDNEV算法依然保持較高的水準(zhǔn),IM算法和CDNEV算法在網(wǎng)絡(luò)規(guī)模擴(kuò)大時(shí)性能差異不明顯,IM算法和CDNEV算法優(yōu)于其他算法,但是IM算法的時(shí)間復(fù)雜度為O(n(m+n)),也高于CDNEV算法的O(nlogn),結(jié)果說(shuō)明,CDNEV算法能夠應(yīng)用于大規(guī)模網(wǎng)絡(luò)上的社團(tuán)劃分.

隨著模擬網(wǎng)絡(luò)節(jié)點(diǎn)和邊的數(shù)量的增加,網(wǎng)絡(luò)結(jié)構(gòu)更加復(fù)雜,導(dǎo)致算法在真實(shí)網(wǎng)絡(luò)和模擬網(wǎng)絡(luò)上的結(jié)果有所下降.但從實(shí)驗(yàn)結(jié)果中可以清晰地看出,隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大,所有算法的性能都在下降,CDNEV算法表現(xiàn)得相對(duì)于其他算法依然有一定優(yōu)勢(shì).

4.4 節(jié)點(diǎn)向量的有效性分析

為了深入分析CDNEV算法生成向量的有效性,我們對(duì)Karate網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行啟發(fā)式隨機(jī)游走,然后采用節(jié)點(diǎn)向量表示算法對(duì)每個(gè)節(jié)點(diǎn)生成一個(gè)二維的分布式向量.

為了驗(yàn)證節(jié)點(diǎn)二維分布式向量的效果,我們用二維向量做散點(diǎn)圖,如圖4所示.圖4中的每個(gè)點(diǎn)代表一個(gè)節(jié)點(diǎn),不同的顏色表示節(jié)點(diǎn)所屬社團(tuán).

從圖4可以看出,雖然只用了二維向量,放棄了部分維度上的信息,但用二維向量作為節(jié)點(diǎn)距離,然后對(duì)節(jié)點(diǎn)聚類(lèi),依然能夠區(qū)分社團(tuán)結(jié)構(gòu).從散點(diǎn)圖可以看出,只有 1個(gè)藍(lán)色的節(jié)點(diǎn)靠近紅色的社團(tuán)、1個(gè)紅色的節(jié)點(diǎn)靠近藍(lán)色的社團(tuán),社團(tuán)之間的重疊區(qū)域較少.隨著維度的增加,社團(tuán)內(nèi)部的節(jié)點(diǎn)距離將會(huì)更加緊密,這樣保證了CDNEV算法生成的節(jié)點(diǎn)分布式向量能夠有效地表示節(jié)點(diǎn)在社團(tuán)結(jié)構(gòu)上的特性.

綜合真實(shí)網(wǎng)絡(luò)和模擬網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果分析,CDNEV算法具有簡(jiǎn)單、有效的特點(diǎn),適合于在大型復(fù)雜的網(wǎng)絡(luò)上進(jìn)行社團(tuán)劃分.

Fig.4 Relationship of 2D vector scatter diagram and community structure圖4 二維向量散點(diǎn)圖與社團(tuán)結(jié)構(gòu)的關(guān)系

5 總結(jié)與未來(lái)工作

本文提出一種結(jié)合自然語(yǔ)言處理方法與聚類(lèi)方法的社團(tuán)劃分算法 CDNEV.CDNEV算法首先通過(guò)啟發(fā)式的隨機(jī)游走算法生成節(jié)點(diǎn)上下文序列,然后將節(jié)點(diǎn)序列類(lèi)比為自然語(yǔ)言處理中的詞序列,使用SkipGram算法學(xué)習(xí)能夠代表每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)特征向量,在學(xué)習(xí)過(guò)程中使用Hierarchical Softmax方法加快特征向量的學(xué)習(xí)速率,最后依據(jù)網(wǎng)絡(luò)中的核心節(jié)點(diǎn),使用K-Means聚類(lèi)方法得到最后復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu).CDNEV算法與其他經(jīng)典的社區(qū)發(fā)現(xiàn)算法在多種真實(shí)網(wǎng)絡(luò)和模擬基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了比較,實(shí)驗(yàn)結(jié)果表明,算法在大多數(shù)數(shù)據(jù)集上具有一定優(yōu)勢(shì),不論在有標(biāo)記網(wǎng)絡(luò)中的F1值,還是在無(wú)標(biāo)記網(wǎng)絡(luò)中的模塊度值都處于較高水準(zhǔn),同時(shí),算法復(fù)雜度較小,執(zhí)行效率快,說(shuō)明CDNEV算法能夠適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分任務(wù),而且能夠保持較高的精度.

在大型網(wǎng)絡(luò)上存在重疊社團(tuán)結(jié)構(gòu),如何構(gòu)造滿足重疊等復(fù)雜社區(qū)結(jié)構(gòu)的節(jié)點(diǎn)向量是一個(gè)值得研究的方向.CDNEV 模型目前僅使用了網(wǎng)絡(luò)的結(jié)構(gòu)信息,在未來(lái)的工作中,還將引入節(jié)點(diǎn)上的文本標(biāo)記等其他信息.另外,研究算法的并行化處理,使得算法能夠應(yīng)用于大規(guī)模網(wǎng)絡(luò)也是值得研究的方向.對(duì)于不同的社團(tuán)劃分算法,還應(yīng)考慮統(tǒng)一開(kāi)發(fā)的實(shí)驗(yàn)語(yǔ)言與運(yùn)行平臺(tái),以便更好地測(cè)試不同算法在實(shí)際應(yīng)用中的執(zhí)行效率.