基于node2vec的社區(qū)檢測(cè)方法?

王慧雪

（1.武漢郵電科學(xué)研究院 武漢 430074）（2.南京烽火天地通信科技有限公司 南京 210019）

1 引言

真實(shí)世界中，大多數(shù)的系統(tǒng)都可以表示為復(fù)雜網(wǎng)絡(luò)。萬(wàn)維網(wǎng)、通信網(wǎng)、交通運(yùn)輸網(wǎng)、電力網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等許多現(xiàn)實(shí)網(wǎng)絡(luò)都與人們的生活密切相關(guān)。復(fù)雜網(wǎng)絡(luò)內(nèi)部，有的節(jié)點(diǎn)相互連接緊密，有的節(jié)點(diǎn)相互連接稀疏，這個(gè)特性叫做網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。發(fā)現(xiàn)這些社區(qū)結(jié)構(gòu)，可以幫助我們分析以及預(yù)測(cè)網(wǎng)絡(luò)中的結(jié)構(gòu)和各個(gè)元素之間的交互關(guān)系，具有非常重要的意義。

針對(duì)社區(qū)檢測(cè)的研究，國(guó)內(nèi)外的學(xué)者們已經(jīng)提出了很多方法。圖分割法是最早的社區(qū)檢測(cè)方法，其中K-L算法和譜平分法［1］比較比較典型。運(yùn)用圖分割法進(jìn)行社區(qū)劃分有一個(gè)明顯的局限，就是需要事先知道社區(qū)的先驗(yàn)信息，即社區(qū)的大小和數(shù)量，因而很難得到精確的劃分結(jié)果。

另一種應(yīng)用廣泛的方法為層次聚類(lèi)法。分為分裂算法和凝聚算法兩類(lèi)。2002年，Girvan和Newman提出了GN算法［2］，是一種分裂算法，其流程為計(jì)算網(wǎng)絡(luò)中每個(gè)連接的邊介數(shù)，然后去掉邊介數(shù)最大的邊直到所有的邊都被刪除。該算法計(jì)算復(fù)雜度較高，不適用于大規(guī)模網(wǎng)絡(luò)。GN算法沒(méi)有終止條件，網(wǎng)絡(luò)最終會(huì)被劃分為單獨(dú)的節(jié)點(diǎn)，對(duì)此，Newman等又提出了一種衡量網(wǎng)絡(luò)劃分質(zhì)量的標(biāo)準(zhǔn)，模塊度Q。模塊度越大，代表著社區(qū)劃分的結(jié)果越好。Newman等2004年提出了一種基于凝聚法的社區(qū)檢測(cè)算法，快速GN搜索算法，F(xiàn)N算法［3］，它的思想是把網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都看成一個(gè)獨(dú)立的社區(qū)并計(jì)算Q值，然后合并有邊相連的兩個(gè)社區(qū)，計(jì)算此時(shí)的模塊度增量ΔQ，選擇增量最大的兩個(gè)社區(qū)合并，重復(fù)這個(gè)過(guò)程，直到整個(gè)網(wǎng)絡(luò)合并為一個(gè)社區(qū)。

近年來(lái)基于模塊度優(yōu)化的算法成為研究的熱點(diǎn)。研究者們提出了許多智能優(yōu)化的算法，如遺傳算法、粒子群算法、模擬退火算法、蟻群算法等。這類(lèi)算法把社區(qū)檢測(cè)問(wèn)題看成一個(gè)優(yōu)化模塊度有關(guān)的目標(biāo)函數(shù)，尋找當(dāng)模塊度達(dá)到最大時(shí)的網(wǎng)絡(luò)劃分。本文不同于以上方法的研究，提出了一種基于node2vec的社區(qū)檢測(cè)方法，利用 node2vec算法［4～6］將社區(qū)檢測(cè)轉(zhuǎn)換為機(jī)器學(xué)習(xí)中的聚類(lèi)問(wèn)題，該方法中首先使用biasα random walk策略［7］生成一系列序列，然后使用Skip-Gram模型［8］去訓(xùn)練特征向量，訓(xùn)練出的特征向量對(duì)節(jié)點(diǎn)之間的同質(zhì)性假設(shè)和結(jié)構(gòu)性假設(shè)都有很好的刻畫(huà)。最后，分別使用K-Means［9］、DBSCAN［10］、SOM 聚類(lèi)算法［11］對(duì)訓(xùn)練出的特征向量進(jìn)行聚類(lèi)，聚類(lèi)的結(jié)果即為最終的社區(qū)劃分，同時(shí)對(duì)這三種聚類(lèi)結(jié)果進(jìn)行對(duì)比分析。本文分別使用人工合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)作為實(shí)驗(yàn)數(shù)據(jù)，通過(guò)仿真證明了本文提出方法的可行性。

2 基于node2vec的社區(qū)檢測(cè)

2.1 隨機(jī)游走策略

2.1.1 隨機(jī)游走

node2vec算法中提出一種帶權(quán)重的隨機(jī)游走算法—biasαrandom walk，該算法可以使訓(xùn)練出的向量同時(shí)滿(mǎn)足節(jié)點(diǎn)之間同性質(zhì)與結(jié)構(gòu)相似性假設(shè)。在該算法中，給定一個(gè)源節(jié)點(diǎn)μ，我們假設(shè)隨機(jī)游走的步長(zhǎng)為固定長(zhǎng)度L，從源節(jié)點(diǎn)μ開(kāi)始，使用如下分布產(chǎn)生鄰居序列：

ci代表隨機(jī)游走中的第i個(gè)節(jié)點(diǎn)，πνx表示節(jié)點(diǎn)ν到節(jié)點(diǎn)的轉(zhuǎn)移概率，Z為歸一化因子。

2.1.2 帶偏置的搜索算子

隨機(jī)游走最簡(jiǎn)單的方法是根據(jù)邊的權(quán)重ωνx抽取下一個(gè)節(jié)點(diǎn)，此時(shí) πνx=ωνx，然而，當(dāng)檢測(cè)兩種不同類(lèi)型的網(wǎng)絡(luò)社區(qū)時(shí)，這并不能劃分出網(wǎng)絡(luò)結(jié)構(gòu)，也不能指導(dǎo)我們?nèi)ニ阉?。另外，不同于BFS和DFS這類(lèi)極端采樣相同結(jié)構(gòu)和性質(zhì)的范例，我們的隨機(jī)游走應(yīng)該適應(yīng)于這樣一個(gè)事實(shí)，即這些相同的節(jié)點(diǎn)并不是競(jìng)爭(zhēng)性和排他性的，真實(shí)世界的網(wǎng)絡(luò)通常表現(xiàn)出BFS和DFS的混合。

我們定義一個(gè)帶有兩個(gè)參數(shù) p和q的二階隨機(jī)游走來(lái)控制游走。假設(shè)隨機(jī)游走要經(jīng)過(guò)邊edge(t，x)，當(dāng)前處于節(jié)點(diǎn)ν。游走到下一步時(shí)需要計(jì)算從節(jié)點(diǎn)ν經(jīng)過(guò)邊edge(t，x)的轉(zhuǎn)移概率。轉(zhuǎn)移概率 πνx=αpq(t，x).ωνx，αpq(t，x)由式（2）給出，其中t表示上一個(gè)節(jié)點(diǎn)，ν代表當(dāng)前節(jié)點(diǎn)，x為下一個(gè)可能的節(jié)點(diǎn)。

如圖1表示了node2vec中的隨機(jī)游走過(guò)程。游走從t到ν，現(xiàn)在需要計(jì)算離開(kāi)節(jié)點(diǎn)ν的下一步驟。邊上的標(biāo)簽代表了帶偏置的搜索算子α。dtx表示節(jié)點(diǎn)t和節(jié)點(diǎn)x之間的最短路徑。

圖1 鄰居節(jié)點(diǎn)估計(jì)示意圖

直觀上來(lái)看，參數(shù) p和q控制搜索速度以及離開(kāi)源節(jié)點(diǎn)μ的鄰域，這兩個(gè)參數(shù)使我們搜尋的過(guò)程在BFS和DFS之間取得平衡，因此，既反映了節(jié)點(diǎn)的同質(zhì)性，又反映了結(jié)構(gòu)相似性。

返回參數(shù) p。參數(shù)p控制返回上一節(jié)點(diǎn)的可能性。給該參數(shù)設(shè)置較大的值可以降低在接下來(lái)的兩個(gè)步驟中采樣到已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)的概率。這種策略?xún)H考慮當(dāng)前節(jié)點(diǎn)的源節(jié)點(diǎn)2-hop內(nèi)的節(jié)點(diǎn)。如果 p值很小，則將會(huì)導(dǎo)致游走在源節(jié)點(diǎn)μ附近。

深度控制參數(shù)q，如果q＞1，則偏向于遍歷臨近t節(jié)點(diǎn)的節(jié)點(diǎn)，這種游走類(lèi)似于BFS；相反，如果q＜1，則偏向于遍歷遠(yuǎn)離t節(jié)點(diǎn)的節(jié)點(diǎn)，這種行為反映了傾向于向外探索的DFS，然而這里的一個(gè)重要區(qū)別是我們實(shí)現(xiàn)的類(lèi)似于DFS的搜索是在隨機(jī)游走的框架下進(jìn)行的。因此，這些采樣的點(diǎn)從給定源節(jié)點(diǎn)并不是非常嚴(yán)格的增加距離，反而使我們受益于簡(jiǎn)單的預(yù)處理和隨機(jī)游走的高效采樣率。

2.2 Skip-Gram模型

Skip-Gram是一種語(yǔ)言模型，該模型能夠極大化單詞出現(xiàn)在上下文中的概率。它是使用一個(gè)單詞來(lái)預(yù)測(cè)句子。該模型優(yōu)化的目標(biāo)函數(shù)由式（3）給出：

其中w表示當(dāng)前詞，Context(w)表示詞的上下文，C表示語(yǔ)料庫(kù)?？梢岳斫鉃樵撃Ｐ拖壤梦谋菊Z(yǔ)料庫(kù)構(gòu)造詞匯表，然后學(xué)習(xí)詞的向量表示。在本文中，該語(yǔ)料庫(kù)為網(wǎng)絡(luò)中的節(jié)點(diǎn)隨機(jī)游走后產(chǎn)生的線性序列。具體模型如圖2所示。

圖2 Skip-Gram模型框架結(jié)構(gòu)

從圖2可看出，該模型由輸入層、映射層和輸出層組成。其中，W1為輸入層和映射層之間的權(quán)重矩陣，W2為映射層和輸出層之間的權(quán)重矩陣。輸入為one-hot編碼的形式，該模型的原理可以理解為在一個(gè)句子或者文本中，選擇任意一個(gè)單詞用其向量表示，使這個(gè)向量能夠預(yù)測(cè)到其周?chē)膯卧~，即該模型的訓(xùn)練目標(biāo)為給一個(gè)單詞序列，使式（4）的值最大。

其中，T為訓(xùn)練文本的大小，c為窗口的大小，wt為任意一個(gè)單詞的向量，wt+j為前后 j個(gè)單詞，計(jì)算條件概率p(wt+j|wt)的公式如下：

其中，w1為當(dāng)前輸入單詞，w0為當(dāng)前輸出單詞，vw和分別是詞的輸入和輸出。本文中，我們把隨機(jī)游走后的線性序列看成輸入的單詞，把經(jīng)過(guò)訓(xùn)練后預(yù)測(cè)到的輸入單詞附近單詞的向量形式作為特征向量，該特征向量攜帶有每個(gè)初始輸入節(jié)點(diǎn)的特征，接下來(lái)對(duì)其進(jìn)行聚類(lèi)。

2.3 特征向量聚類(lèi)

上面我們使用node2vec算法對(duì)節(jié)點(diǎn)進(jìn)行訓(xùn)練后，得到網(wǎng)絡(luò)節(jié)點(diǎn)的最佳特征表示，如何對(duì)這些特征進(jìn)行聚類(lèi)，劃分社區(qū)結(jié)構(gòu)是我們需要重點(diǎn)關(guān)注的問(wèn)題。

目前有大量的聚類(lèi)算法，但不同的方法適用于不同類(lèi)型的數(shù)據(jù)，想要得到好的聚類(lèi)結(jié)果，可以通過(guò)對(duì)相同的數(shù)據(jù)嘗試多種聚類(lèi)算法。在本文中，我們選用基于劃分的方法K-Means算法、基于密度的方法DBSCAN算法、基于模型的方法SOM算法這三種算法對(duì)特征向量進(jìn)行聚類(lèi)。

K-Means算法是劃分方法中較為經(jīng)典的算法，該算法效率很高，但需要事先指定劃分簇?cái)?shù)k，針對(duì)k值的確定，本文先使用傳統(tǒng)的社區(qū)檢測(cè)算法進(jìn)行社區(qū)檢測(cè)，然后把檢測(cè)結(jié)果中社區(qū)的個(gè)數(shù)作為K-Means算法中的k值。

DBSCAN算法是一種基于密度的聚類(lèi)算法，不需要事先確定劃分的簇?cái)?shù)，而且其最大的優(yōu)點(diǎn)為能夠發(fā)現(xiàn)任意形狀的簇，聚類(lèi)效果較好。

SOM聚類(lèi)算法是一種競(jìng)爭(zhēng)學(xué)習(xí)型的無(wú)監(jiān)督神經(jīng)網(wǎng)絡(luò)算法，它通過(guò)自動(dòng)尋找樣本中的內(nèi)在規(guī)律和本質(zhì)屬性，自組織、自適應(yīng)地改變網(wǎng)絡(luò)參數(shù)和結(jié)構(gòu)。

這三種聚類(lèi)算法各有優(yōu)劣，我們需要通過(guò)實(shí)驗(yàn)進(jìn)一步證明使用哪種聚類(lèi)算法聚類(lèi)特征向量，社區(qū)檢測(cè)的準(zhǔn)確率更高。

3 算法流程

基于node2vec的社區(qū)檢測(cè)方法的流程圖如圖3所示。

圖3 基于node2vec社區(qū)檢測(cè)方法流程圖

基于node2vec的社區(qū)檢測(cè)方法步驟如下：

輸入：鄰接矩陣表示的網(wǎng)絡(luò)圖G(V，E)

輸出：對(duì)網(wǎng)絡(luò)劃分的結(jié)果

步驟1：轉(zhuǎn)移概率預(yù)處理。定義由當(dāng)前節(jié)點(diǎn)轉(zhuǎn)移到下一節(jié)點(diǎn)的概率πνx；

步驟2：隨機(jī)游走。根據(jù)轉(zhuǎn)移概率的預(yù)處理得到G，(V，E，π)，以網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)為初節(jié)點(diǎn)進(jìn)行隨機(jī)游走；

步驟3：使用Skip-Gram模型訓(xùn)練特征向量。輸入為步驟2隨機(jī)游走后得到的線性序列，目標(biāo)是對(duì)隱藏層進(jìn)行優(yōu)化，希望輸入為某個(gè)節(jié)點(diǎn)時(shí)，輸出為其同質(zhì)性或同構(gòu)性的節(jié)點(diǎn)的概率最大。優(yōu)化的過(guò)程如下：

1）前向傳播：對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行one-hot編碼，初始化隱層加權(quán)矩陣Φ：WN×d和隱層-輸出層加權(quán)矩陣，在輸出層計(jì)算條件似然概率，并與預(yù)測(cè)節(jié)點(diǎn)的one-hot向量求差作為誤差向量；計(jì)算各誤差向量對(duì)應(yīng)的元素和；

2）反向傳播：根據(jù)前向傳播過(guò)程中產(chǎn)生的誤差，采用鏈?zhǔn)角髮?dǎo)法則，將其反向傳播到隱層，更新權(quán)重矩陣，采用更新過(guò)的加權(quán)矩陣，迭代前向傳播過(guò)程，直到條件似然概率取得最大值，此時(shí)隱層加權(quán)矩陣即為網(wǎng)絡(luò)節(jié)點(diǎn)的最佳特征表示。

步驟4：使用K-Means聚類(lèi)算法、DBSCAN聚類(lèi)算法、SOM聚類(lèi)算法對(duì)步驟3得到的特征向量進(jìn)行聚類(lèi)；

步驟5：得出劃分結(jié)果，并對(duì)比使用三種聚類(lèi)算法得到的網(wǎng)絡(luò)劃分的優(yōu)劣。

4 實(shí)驗(yàn)仿真

4.1 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

標(biāo)準(zhǔn)化互信息（NMI）［12］常用在聚類(lèi)中，度量?jī)蓚€(gè)聚類(lèi)結(jié)果的相近程度，在社區(qū)檢測(cè)中是衡量真實(shí)的網(wǎng)絡(luò)劃分與社區(qū)檢測(cè)得到的網(wǎng)絡(luò)劃分相似性的方法。對(duì)于兩個(gè)不同的劃分結(jié)果A和B，NMI定義如下。

其中，N為節(jié)點(diǎn)的個(gè)數(shù)，C是一個(gè)混合矩陣，其中的元素Cij表示劃分結(jié)果A中的社區(qū)i在劃分結(jié)果B中的社區(qū) j里面也出現(xiàn)的個(gè)數(shù)。CA表示劃分結(jié)果A中社區(qū)的個(gè)數(shù)，CB表示劃分結(jié)果B中社區(qū)的個(gè)數(shù)。Ci?中表示C中第i行元素的總和，C?j表示第 j列元素的總和。NMI值越大，A劃分和B劃分的相似度越大，當(dāng)NMI為1時(shí)，說(shuō)明A和B的劃分完全一致。

Newman 和 Girvan 定義了模塊度［13］（modulari?ty）為評(píng)價(jià)網(wǎng)絡(luò)社區(qū)劃分優(yōu)劣的指標(biāo)。Newman認(rèn)為一個(gè)合理的社區(qū)就是將劃分出的網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)進(jìn)行比較，劃分出的網(wǎng)絡(luò)與隨機(jī)網(wǎng)絡(luò)的期望差值越大，表明該網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越明顯。模塊度可定義為如下。

其中，m為網(wǎng)絡(luò)的總邊數(shù)，Avw有兩種取值，取值為1時(shí)代表節(jié)點(diǎn)v與節(jié)點(diǎn)w之間有連接的邊，取值為0時(shí)代表節(jié)點(diǎn)v與節(jié)點(diǎn)w之間無(wú)連接的邊，kv為節(jié)點(diǎn)v的度，當(dāng)節(jié)點(diǎn)v與節(jié)點(diǎn)w在同一個(gè)社區(qū)時(shí)，δ(cv，cw)=1，否則為0。

4.2 人工合成網(wǎng)絡(luò)

本文所使用的人工合成網(wǎng)絡(luò)是Lancichinetti等提出的基準(zhǔn)網(wǎng)絡(luò)，該模型引入了一個(gè)混合參數(shù)μ來(lái)調(diào)節(jié)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，該參數(shù)表示的是社區(qū)內(nèi)節(jié)點(diǎn)和外節(jié)點(diǎn)的連接緊密程度，通過(guò)調(diào)節(jié)該參數(shù)，可以給實(shí)驗(yàn)提供包含不同社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)類(lèi)型，μ越小，表明社區(qū)結(jié)構(gòu)越清晰，網(wǎng)絡(luò)越具有較強(qiáng)的社區(qū)結(jié)構(gòu)，隨著μ的增大，網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越模糊。μ的物理含義是節(jié)點(diǎn)外度占總節(jié)點(diǎn)的比例，以0.5為界，小于0.5時(shí)，說(shuō)明節(jié)點(diǎn)內(nèi)度大于節(jié)點(diǎn)外度，具有較強(qiáng)的社區(qū)結(jié)構(gòu)；大于0.5時(shí)，說(shuō)明節(jié)點(diǎn)內(nèi)度大于節(jié)點(diǎn)外度，網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)較模糊。我們以0.5為界，在0～0.5之間均勻的選取11個(gè)點(diǎn)進(jìn)行實(shí)驗(yàn)。

我們將使用K-Means聚類(lèi)的基于node2vec的社區(qū)檢測(cè)算法簡(jiǎn)稱(chēng)為NK（Community Detection Based on Node2vec By Using K-Means）；使用 DB?SCAN聚類(lèi)的基于node2vec的社區(qū)檢測(cè)算法簡(jiǎn)稱(chēng)為ND（Community Detection Based on Node2vec By Us?ing DBSCAN）；使用SOM聚類(lèi)的基于node2vec的社區(qū)檢測(cè)算法簡(jiǎn)稱(chēng)為NS（Community Detection Based on Node2vec By Using SOM）。本文將NK算法、ND算法、NS算法與傳統(tǒng)的社區(qū)檢測(cè)算法GN算法、Louvain算法在人工合成網(wǎng)絡(luò)上進(jìn)行對(duì)比實(shí)驗(yàn)。

從圖4可以看出，當(dāng) μ≤0.3時(shí)，NK、ND、NS、GN、Louvain算法的NMI值都為1，此時(shí)它們都能準(zhǔn)確的發(fā)現(xiàn)網(wǎng)絡(luò)真實(shí)的社區(qū)結(jié)構(gòu)，從μ開(kāi)始，傳統(tǒng)社區(qū)檢測(cè)算法GN算法、Louvain算法的NMI值開(kāi)始下降，表明社區(qū)檢測(cè)的結(jié)果越來(lái)越不準(zhǔn)確，ND算法在 μ=0.35時(shí)NMI值開(kāi)始呈下降趨勢(shì)，而當(dāng)μ=0.4時(shí)，NK、NS算法的NMI值才開(kāi)始下降，這說(shuō)明了當(dāng)社區(qū)的結(jié)構(gòu)模糊度有所降低時(shí)，基于node2vec的社區(qū)檢測(cè)方法比傳統(tǒng)的算法劃分的更準(zhǔn)確，當(dāng)μ繼續(xù)降低，大于0.4時(shí)，此時(shí)社區(qū)的結(jié)構(gòu)已經(jīng)變得更加模糊，傳統(tǒng)算法GN算法和Louvain算法迅速下降到0.4以下，而基于node2vec的社區(qū)檢測(cè)方法的NMI始終高于對(duì)比算法，其中NS算法在μ=0.5時(shí)NMI值還達(dá)到0.45左右。綜上所述，基于node2vec的社區(qū)檢測(cè)算法在人工合成網(wǎng)絡(luò)中性能更加優(yōu)越。

圖4 各算法在Benchmark網(wǎng)絡(luò)上NMI對(duì)比

4.3 真實(shí)世界網(wǎng)絡(luò)

本文使用四個(gè)經(jīng)典的真實(shí)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)仿真，分別為空手道俱樂(lè)部網(wǎng)絡(luò)（Karate Network）、海豚網(wǎng)絡(luò)（Dolphins Network）、美國(guó)足球聯(lián)賽網(wǎng)絡(luò)（Foot?ball Network）、美國(guó)政治書(shū)網(wǎng)絡(luò)（Books Network），下表給出了這四個(gè)真實(shí)網(wǎng)絡(luò)的邊和節(jié)點(diǎn)信息。

表1 四種真實(shí)網(wǎng)絡(luò)的特性

對(duì)于這四個(gè)真實(shí)網(wǎng)絡(luò)，本文把基于node2vec的社區(qū)檢測(cè)方法和對(duì)比算法獨(dú)立運(yùn)行了20次，使用模塊度Q作為評(píng)價(jià)指標(biāo)，選出最大Q值（Qmax）和平均Q值（Qavg）圖5為實(shí)驗(yàn)結(jié)果。

從圖5可以看出，基于node2vec的社區(qū)檢測(cè)方法NK、ND、NS算法在四個(gè)真實(shí)數(shù)據(jù)集下與傳統(tǒng)社區(qū)檢測(cè)算法GN算法、Louvain算法相比較，Q值有所增大，說(shuō)明新算法社區(qū)檢測(cè)的準(zhǔn)確率有了提高。其中NK算法總體要優(yōu)于ND算法，但NK算法有一個(gè)弊端，就是要事先給定劃分的簇?cái)?shù)，對(duì)此本文將傳統(tǒng)算法檢測(cè)出的社區(qū)個(gè)數(shù)作為NK算法確定簇?cái)?shù)的依據(jù)。NS算法在Karate網(wǎng)絡(luò)和Dolphins網(wǎng)絡(luò)中檢測(cè)準(zhǔn)確率最高，隨著數(shù)據(jù)量的增大，出現(xiàn)學(xué)習(xí)過(guò)度的現(xiàn)象，在Football和Books網(wǎng)絡(luò)中檢測(cè)準(zhǔn)確率有所降低。

圖5 幾種算法在四個(gè)真實(shí)網(wǎng)絡(luò)下的模塊度對(duì)比

本文通過(guò)實(shí)驗(yàn)證明了基于node2vec的社區(qū)檢測(cè)方法的有效性，與傳統(tǒng)的社區(qū)檢測(cè)方法GN、Lou?vain相比，具有很強(qiáng)的競(jìng)爭(zhēng)力。

5 結(jié)語(yǔ)

本文提出了基于node2vec的社區(qū)檢測(cè)方法，該方法首先使用node2vec算法把網(wǎng)絡(luò)中的節(jié)點(diǎn)通過(guò)訓(xùn)練轉(zhuǎn)換成網(wǎng)絡(luò)節(jié)點(diǎn)的最佳特征表示，再選取三種典型的聚類(lèi)算法對(duì)該特征進(jìn)行聚類(lèi)，聚類(lèi)的結(jié)果即為社區(qū)的劃分結(jié)果。使用node2vec算法的關(guān)鍵在于將社區(qū)檢測(cè)轉(zhuǎn)化為機(jī)器學(xué)習(xí)中的聚類(lèi)問(wèn)題。本文通過(guò)實(shí)驗(yàn)比較了這三種聚類(lèi)算法的優(yōu)劣，同時(shí)，實(shí)驗(yàn)對(duì)比了傳統(tǒng)的社區(qū)檢測(cè)算法GN算法、Louvain算法，證明了基于node2vec的社區(qū)檢測(cè)方法的有效性。