韓忠明,劉 雯,李夢琪,鄭晨燁,譚旭升,段大高

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

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

1 引 言

如何準確、高效地進行社團結(jié)構(gòu)劃分是當前復(fù)雜網(wǎng)絡(luò)理論研究領(lǐng)域中的熱點問題.很多復(fù)雜的系統(tǒng)可以轉(zhuǎn)化為由節(jié)點和邊組成的網(wǎng)絡(luò)來進行建模,如人與人之間的關(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ò)中一個十分重要的性質(zhì)是社團結(jié)構(gòu),理解社團結(jié)構(gòu)對理解網(wǎng)絡(luò)的整體具有重要價值.Newman把社團結(jié)構(gòu)定義為網(wǎng)絡(luò)中的若干個群體或者團體,群體內(nèi)部的節(jié)點間存在緊密連接,群體間的連接則相對稀疏[1].

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

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

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

2 研究現(xiàn)狀

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

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

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

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

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

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

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

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

Table 1 Main symbols表1 主要符號列表

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

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

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

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

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

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

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

定義2(k-step概率).令e∈E表示圖G的一條邊,k-step概率Pk(e)表示從當前節(jié)點進行隨機游走過程選擇通過邊e的概率.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 分布式節(jié)點表達向量生成

3.2.1 統(tǒng)計語言模型

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

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

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

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

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

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

3.2.2 SkipGram模型

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

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

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

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

3.2.3 Hierarchical Softmax方法

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

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

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

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

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

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

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

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

令:

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

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

3.3 聚類算法

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

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

3.4 CDNEV算法整體流程

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

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

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

4 實驗結(jié)果與分析

我們從優(yōu)化方法和啟發(fā)式方法中選取10種經(jīng)典的社團發(fā)現(xiàn)算法進行對比分析和比較,包括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)算法進行了比較.在用 DeepWalk算法繼續(xù)進行社團劃分時,我們采取了和本文算法一致的策略,也就是說,在學(xué)習(xí)到節(jié)點向量的基礎(chǔ)上用K-Means算法進行聚類,從而得到社團劃分的結(jié)果.

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

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

4.1 算法結(jié)果評價指標

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

(1) 準確率(precision,簡稱P)

準確率代表社團劃分結(jié)果中正確節(jié)點數(shù)量占總節(jié)點數(shù)量的比例,計算方法為

其中,Lresult表示算法得到的社團,Lture表示真實社團.

(2) 召回率(recall,簡稱R)

召回率反映了真實社團中被正確劃分出的節(jié)點的比例,計算方法為

(3)F指標(F1)

F1評價指標是對P值和R值的綜合,計算公式為

其中,P為準確率,R為召回率.

(4) 模塊度(modularity)

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

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

(5) 標準化互信息(normalized mutual information,簡稱NMI)

標準化互信息用來評價聚類效果.其中,U對應(yīng)標準結(jié)果,V對應(yīng)聚類的預(yù)測結(jié)果,計算方法為

其中,

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

調(diào)整蘭德系數(shù)用來評價聚類結(jié)果的準確程度,計算方法為

其中,

其中,a表示標準結(jié)果與預(yù)測結(jié)果相同的樣本數(shù)量,b表示標準結(jié)果與預(yù)測結(jié)果不相同的樣本數(shù)量.

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

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

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

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

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

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

在一些特殊情況下,如SG算法和LE算法,在Karate數(shù)據(jù)集上的準確率也可以達到100%,但這些算法是將一個大社團中的節(jié)點劃分到多個子社團,這種“過度劃分”導(dǎo)致它們的召回率很低,所以最終的F1值較低.由第3.5節(jié)易知,由于SG算法是基于貪心迭代算法的一種改進,因此,SG算法相較于CDNEV算法,其時間復(fù)雜度較高. CDNEV算法與其他算法在E-mail網(wǎng)絡(luò)上的模塊度比較可見表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ò)是標記網(wǎng)絡(luò),且網(wǎng)絡(luò)規(guī)模較大,各算法在社團劃分上的ARI指標見表5,CDNEV算法的ARI指標與IM、N2V等算法基本持平,高于其他算法.驗證了CDNEV算法在較大規(guī)模網(wǎng)絡(luò)中的可擴展性.

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

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

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

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

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

按照文獻[59]中的實驗設(shè)計建議,對LFR基準網(wǎng)絡(luò)的參數(shù)設(shè)置如下.

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

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

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

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

我們通過設(shè)置LFR,模擬不同參數(shù),進行了3組實驗.

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

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

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

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

Fig.1 The variation of different algorithms’F1 with differentμ on base networks, n=1000,cmin=10,cmax=50圖1 不同算法在基準網(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ù)μ取不同值時,得到對應(yīng)的F1值.圖1和圖2的2個子圖是CDNEV和不同算法的比較曲線.圖1和圖2的橫軸表示μ值,縱軸表示F1值.

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

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

Fig.2 The variation of different algorithms’F1 with differentμ on base networks, n=1000,cmin=20,cmax=100圖2 不同算法在基準網(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 不同算法在基準網(wǎng)絡(luò)規(guī)模變化下的F1值

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

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

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

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

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

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

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

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

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

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

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