李叢正，梁 壘，周 強

（1.青島大學(xué) 數(shù)據(jù)科學(xué)與軟件工程學(xué)院，山東 青島 266000；2.浙江大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，浙江 杭州 310027）

0 引 言

本文研究的多關(guān)系網(wǎng)絡(luò)的邊的類型有多種，其屬于異構(gòu)網(wǎng)絡(luò)的一類[1]。社區(qū)發(fā)現(xiàn)是在網(wǎng)絡(luò)上進行數(shù)據(jù)分析時的重要工作，它的目的是對網(wǎng)絡(luò)上的節(jié)點進行劃分，使得劃分在一個組內(nèi)的節(jié)點間聯(lián)系盡量緊密，不同組的節(jié)點之間聯(lián)系相對稀疏[2]。其在挖掘網(wǎng)絡(luò)結(jié)構(gòu)，揭示群體行為等方面有著重要意義，因此近些年來有大量相關(guān)方面的研究。傳統(tǒng)的方法一般是基于單關(guān)系網(wǎng)絡(luò)，例如基于遺傳算法的方法[3]、基于信息熵的算法[4]、譜聚類算法[5]、基于模塊度的算法[6]等。在多關(guān)系網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)方面，文獻[7]提出的CDMN 算法建立了多關(guān)系網(wǎng)絡(luò)模型并定義了節(jié)點影響力，實現(xiàn)多關(guān)系網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)。文獻[8]使用RCA 技術(shù)對多關(guān)系學(xué)術(shù)網(wǎng)絡(luò)進行建模并在此基礎(chǔ)上進行社區(qū)發(fā)現(xiàn)。MultiNetCom 算法將原多關(guān)系網(wǎng)絡(luò)拆分成多個單關(guān)系網(wǎng)絡(luò)，在每個單關(guān)系網(wǎng)絡(luò)上分別做聚類操作后再依據(jù)節(jié)點對各個類的從屬關(guān)系將多個單關(guān)系網(wǎng)絡(luò)融合成一個單關(guān)系網(wǎng)絡(luò)進行社區(qū)發(fā)現(xiàn)[9]。文獻[10]使用關(guān)系貝葉斯模型對多關(guān)系網(wǎng)絡(luò)進行建模。以往的工作或是對原網(wǎng)絡(luò)做轉(zhuǎn)換，或是考慮不同關(guān)系間的相互影響及關(guān)系強度對網(wǎng)絡(luò)進行重新建模再進行社區(qū)劃分，并沒有直接在多關(guān)系網(wǎng)絡(luò)上利用節(jié)點間的各種關(guān)系對節(jié)點進行劃分，網(wǎng)絡(luò)的多關(guān)系信息存在丟失。

針對上述社區(qū)發(fā)現(xiàn)中存在的不足，本文提出基于機器學(xué)習(xí)的多關(guān)系網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法，在考慮到不同類型邊之間的差異的前提下，使用本文定義的方法計算不同類型邊的權(quán)重，再利用本文設(shè)計的多關(guān)系網(wǎng)絡(luò)數(shù)據(jù)采集策略直接在多關(guān)系網(wǎng)絡(luò)上提取訓(xùn)練數(shù)據(jù)，然后利用采集到的數(shù)據(jù)訓(xùn)練多關(guān)系網(wǎng)絡(luò)節(jié)點表示模型，得到網(wǎng)絡(luò)上每個節(jié)點對應(yīng)的向量表示，最后對向量空間中的向量進行聚類，同一個類中的向量所對應(yīng)的網(wǎng)絡(luò)上的節(jié)點則屬于同一個社區(qū)。

1 相關(guān)工作

Mikolov 等提出的word2vec 在自然語言處理領(lǐng)域有著重要的地位，它利用深度神經(jīng)網(wǎng)絡(luò)模型，基于大規(guī)模語料進行訓(xùn)練，然后用低維且稠密的向量表示語料中的單詞。其中一個深度模型是Skip-gram。Skip-gram 是在一個句子上用滑動窗口w采樣，然后最大化出現(xiàn)在同一個窗口w中的中心單詞和鄰居單詞的共現(xiàn)概率。

式中：vi是窗口內(nèi)的中心單詞；vi-w～vi+w是其上下文單詞；φ(vi)是節(jié)點vi映射在向量空間中的向量。通過梯度下降等方式更新φ(vi)，得到最終的向量表示。由式（1）可知，單詞的上下文集合相似時，它們的向量表示也是相似的。從幾何角度講，這些向量的距離更相近。例如，圖1 所示的例子中表示的是一些經(jīng)過訓(xùn)練的詞向量在二維空間中的可視化表示。

圖1 詞嵌入的實例

語義相近的詞（例如動物類中的COW 和LION）因為在訓(xùn)練的語料中有著相比于其他類中的詞（例如ASIA）而言更加相似的上下文單詞集合，所以在經(jīng)過大量數(shù)據(jù)訓(xùn)練后，它們的表示向量也會更加相似，在二維可視化的展示中表現(xiàn)為更加“臨近”。用K-means 等聚類算法對這些詞的表示向量進行聚類則可以將上下文相近的詞（例如COW 和LION）歸為一類。

2 基于機器學(xué)習(xí)的多關(guān)系網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法

定義多關(guān)系網(wǎng)絡(luò)G=(V,E,W)，式中的V={V0,V1,V2,…,Vn}為節(jié)點集合，E={E0,E1,E2,…,Em}為邊的 集 合 ，W={W0,W1,W2,…,W m} 為 邊 的 權(quán) 重 。node2vec[11]等算法設(shè)計了先在網(wǎng)絡(luò)上游走，得到游走的節(jié)點序列，然后將序列類比自然語言中的句子，序列中的節(jié)點類比單詞，再計算節(jié)點的表示向量。本文設(shè)計了面向多關(guān)系網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的游走采樣策略，得到節(jié)點序列，利用滑動窗口從節(jié)點序列中生成訓(xùn)練數(shù)據(jù)，然后對本文提出的節(jié)點表示模型進行訓(xùn)練，進而得到節(jié)點的向量表示。因為社區(qū)劃分的定義為將網(wǎng)絡(luò)中相互聯(lián)系比較緊密的節(jié)點劃入到同一個社區(qū)，如果用滑動窗口在游走得到的節(jié)點序列上滑動取得訓(xùn)練數(shù)據(jù)時，聯(lián)系緊密的節(jié)點有相似的上下文集合，那么這些節(jié)點的向量表示也會相似，而且出現(xiàn)在同一個節(jié)點序列上的兩個節(jié)點A和B，即使不能在滑動窗口取得訓(xùn)練數(shù)據(jù)時有相似的上下文集合，由于同一個節(jié)點序列上其他節(jié)點的影響，A和B的向量表示在經(jīng)過更新計算后相比于未和A，B出現(xiàn)在一個節(jié)點序列的其他節(jié)點也會更相似。

如圖2 所示，在節(jié)點序列＜a,b,c,d,e,f,g,h,i,j,k,l＞上使用長度為5 的滑動窗口獲取訓(xùn)練數(shù)據(jù)。當(dāng)c為中心節(jié)點時，其上下文為集合{a,b,d,e}，j為中心節(jié)點時，其上下文節(jié)點集合為{h,i,k,l}，兩個集合無交集，可知c和j的上下文節(jié)點集合無相似性。但是在g為中心節(jié)點時，其上下文節(jié)點集合為{e,f,h,i}，與c及j的上下文的交集分別為{e}和{h,i}，所以c和j的表示向量會在一定程度上與g的表示向量相似，進而可得c和j的向量表示也會在一定程度相似。由此可以證明，如果能讓聯(lián)系緊密的節(jié)點有更高的頻率出現(xiàn)在同一個游走得到的序列上，同時訓(xùn)練時選擇合適的滑動窗口（在保證對模型訓(xùn)練量不會過大的情況下窗口越長越好）來提取訓(xùn)練數(shù)據(jù)，在經(jīng)過大量訓(xùn)練數(shù)據(jù)訓(xùn)練后，它們的向量表示就會更加相似，再進行聚類后它們就更有可能分在同一個類中，由此實現(xiàn)將聯(lián)系緊密的節(jié)點劃分入同一個社區(qū)中。

本文提出的MLCDM 算法計算節(jié)點的向量表示的流程如圖3 所示。

首先在原網(wǎng)絡(luò)上進行面向社區(qū)發(fā)現(xiàn)的游走，并將游走得到的路徑集合P={P0,P1,P2,…,Pm}記錄下來，然后計算在滑動窗口w里，中心節(jié)點vi與其上下文節(jié)點vj的共現(xiàn)概率，使用梯度下降方法進行更新計算，訓(xùn)練節(jié)點的表示模型，最終得出網(wǎng)絡(luò)上節(jié)點的向量表示。

圖2 節(jié)點序列上提取訓(xùn)練數(shù)據(jù)

圖3 節(jié)點的向量表示的計算流程

2.1 游走采樣

游走的目的是得到若干條面向社區(qū)發(fā)現(xiàn)的游走采樣路徑的集合P={P0,P1,P2,…,Pm}。每條路徑的形式為一個節(jié)點序列＜v1,v2,…,vk＞，在同一個序列中相鄰兩點間游走的邊是圖上的同一類邊。

GN 等算法指出，介數(shù)中心性大的邊更有可能是社區(qū)之間的連接邊，所以本文設(shè)計的游走策略更傾向于選擇介數(shù)中心性小的邊，這樣就會有更大的概率是在同屬一個社區(qū)同時聯(lián)系緊密的節(jié)點間進行游走，所以在游走采樣前先對每條邊的介數(shù)中心性進行計算。

針對多關(guān)系網(wǎng)絡(luò)，第一步游走要確定這條采樣路徑要游走的邊的類別，第一步選擇邊時是在當(dāng)前節(jié)點的臨邊中隨機選擇，未考慮介數(shù)中心性。

式中：Enow是當(dāng)前節(jié)點的集合；Pr(e)是此節(jié)點的每條臨邊被選中的概率。

在接下來第二步、第三步等進行游走時，當(dāng)前節(jié)點的某條臨邊被選到的概率用式（3）計算。首先選出和上一步游走一樣種類的邊，然后對其依據(jù)介數(shù)中心性從小到大進行排序，將其中的前50%（符合要求的臨邊數(shù)不是2 的倍數(shù)則選擇前（符合要求臨邊數(shù)+1）×50%）條邊存入集合ET，然后在ET中隨機選擇一條邊進行游走。

算法1：面向社區(qū)發(fā)現(xiàn)的多關(guān)系網(wǎng)絡(luò)游走

Input：多關(guān)系網(wǎng)絡(luò)G，網(wǎng)絡(luò)節(jié)點數(shù)N，節(jié)點按照0，1，2，…，N-1進行編號，游走路徑的最大長度D，以每個節(jié)點作為開始節(jié)點進行游走的次數(shù)C，邊的種類數(shù)Q

Output：游走采樣得到的集合Walk

1. 初始化節(jié)點序列的集合Walk={Walk0,Walk1，…，WalkQ}

Walkm是游走類型為Em的邊時得到的節(jié)點序列集合

初始化 Walk0,Walk1，…，WalkQ都為空

2. fori=0 toNdo

3. //以節(jié)點Vi為起點開始游走

4. forc=0 toCdo

5. ford=0 toDdo

6. if（d==0）then

7. 按照式（2）得到臨邊被選到的概率，選擇第一步游走的邊（Em），記錄游走到的節(jié)點

8. else

9. 按照式（3）得到臨邊被選到的概率，選擇下一步游走的邊，記錄游走到的節(jié)點

10. END for

11. 將節(jié)點序列按照游走的邊的類別（Em）存入相應(yīng)的集合（Walkm）

12. END for

13. END for

14. return Walk

2.2 計算每個節(jié)點對應(yīng)的向量表示

在上一步游走采樣得到的路徑上用長度為k的窗口從路徑的起點開始滑動，依次對窗口當(dāng)前中心點的向量表示進行更新計算。例如在圖3 中的第二步，游走得到的節(jié)點序列為＜v1,v2,v3,v4,v5＞，其長度為5，滑動窗口的長度取3，當(dāng)中心節(jié)點為v3時，上下文節(jié)點為{v2，v4}。節(jié)點vj作為節(jié)點vi上下文的概率，即共現(xiàn)概率可以被定義為：

式中：uk為節(jié)點vk的向量表示為圖上所有節(jié)點的數(shù)量。當(dāng)把網(wǎng)絡(luò)上的不同類型的邊同等看待時，可以得到目標(biāo)函數(shù)：

通過更新計算式（4）中節(jié)點的向量表示，最小化式（5）。其中：Walk 是所有的游走路徑的集合；k是滑動窗口的長度；（vi,vj）∽Walk∽k表示在游走路徑上滑動長度為k的滑動窗口滑動到某一個位置時，窗口的中心節(jié)點為Vi，而Vj為其上下文節(jié)點集合中的節(jié)點。為了更好地實現(xiàn)多關(guān)系網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)，在開始計算向量的表示前先計算不同類型的邊在社區(qū)發(fā)現(xiàn)時的權(quán)重。本文定義權(quán)重的計算方法為式（6），在已知正確社區(qū)劃分結(jié)果的網(wǎng)絡(luò)上計算不同類型邊的權(quán)重，然后將權(quán)重應(yīng)用到邊類型相同的另一個網(wǎng)絡(luò)上進行社區(qū)劃分。設(shè)有n+1 類邊，編號為 0，1，2，…，n，em表示編號為m的邊落在社區(qū)內(nèi)部的數(shù)量，Em表示編號為m的邊在網(wǎng)絡(luò)上的總邊數(shù)，W m為編號為m的邊的權(quán)重。則：

當(dāng)使用Walkm（算法1 的輸出）中取得的數(shù)據(jù)更新計算節(jié)點的向量表示時，將式（6）結(jié)合式（4）和式（5）得到目標(biāo)函數(shù)為：

使用Walkm中取得的數(shù)據(jù)更新計算節(jié)點的向量表示時，對應(yīng)的中心節(jié)點與鄰居節(jié)點的共現(xiàn)概率為Pm。

2.3 模型優(yōu)化

按照2.2 節(jié)中的方法計算上下文節(jié)點與中心節(jié)點的共現(xiàn)概率P時，計算量比較大而且花費的時間長。為了提高計算效率，縮短計算時間，本文引入負(fù)采樣的計算方法[11]。例如式（7）中的某一個中心節(jié)點Vi和它某一個上下文節(jié)點Vj組成的節(jié)點對（vi,vj），可得目標(biāo)函數(shù)為：

節(jié)點的向量表示是用梯度下降法（SGD）計算的。例如，利用在Walkm中的路徑上用滑動窗口取得的數(shù)據(jù)（vi,vj）對vi的表示ui更新計算時為：

2.4 聚 類

本文使用的聚類算法是K-means。K-means 有很多優(yōu)點，例如收斂速度快、聚類效果優(yōu)、模型可解釋性強等。但它也有不足，原算法初始簇中心點是隨機選擇的，聚類時簇中心點的選擇會直接影響最終的聚類結(jié)果。本文在聚類前先對節(jié)點的接近中心性進行計算，選擇接近中心性較大的作為中心點，以達到更好的聚類效果。

算法2：MLCDM

Input：多關(guān)系網(wǎng)絡(luò)G1，與G1的邊的類型相同的先驗數(shù)據(jù)集G2，網(wǎng)絡(luò)G1的節(jié)點數(shù)N，游走路徑長度D，滑動窗口的長度k，以每個節(jié)點為起始節(jié)點進行游走的次數(shù)C，節(jié)點表示向量的維度dim，邊的種類數(shù)Q，社區(qū)數(shù)目A

Output：社區(qū)劃分結(jié)果R={R0,R1,R2，…，RA-1}//Ra為屬于社區(qū)a的節(jié)點集合

1 利用先驗數(shù)據(jù)集G2及式（6）計算不同種類的邊的權(quán)重

2 在G1上執(zhí)行算法1，得到節(jié)點序列集合Walk={Walk0,Walk1，…，WalkQ}

3 forq=0 toQdo

4 fora=0 to Size Of（Walkq）//遍歷Walkq中每條路徑

5 在Walkta(Walkt中的第a+1 條路徑）上把長度為k的滑動窗口從頭滑動到尾，提取訓(xùn)練數(shù)據(jù)，并用式（13）對節(jié)點的向量表示進行更新計算。

6 END For

7 END For

8 利用式（14）計算節(jié)點的中心性，并選取中心性較大的作為簇中心

9 使用K-means 對節(jié)點的表示向量進行聚類，同一類中的向量對應(yīng)的節(jié)點被分到一個社區(qū)，得到R

10 returnR

3 實 驗

為了驗證MLCDM 算法的性能，本文分別在單關(guān)系網(wǎng)絡(luò)和多關(guān)系網(wǎng)絡(luò)上進行實驗，本實驗共使用6 個數(shù)據(jù)集，2 個單關(guān)系網(wǎng)絡(luò)，4 個多關(guān)系網(wǎng)絡(luò)。

3.1 單關(guān)系網(wǎng)絡(luò)上的實驗

首先在有已知正確社區(qū)劃分結(jié)果的單關(guān)系網(wǎng)絡(luò)上進行實驗。在這里選擇兩個常用的單關(guān)系網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的數(shù)據(jù)集、Zachary 俱樂部網(wǎng)絡(luò)和Dolphin 社交網(wǎng)絡(luò)。Dolphin 網(wǎng)絡(luò)有62個節(jié)點、160條邊，Zachary 網(wǎng)絡(luò)有34個節(jié)點、78條邊。這兩個數(shù)據(jù)集的官方公布社區(qū)數(shù)均為2。將本文提出的MLCDM 算法與CDCDA 算法[12]及MNDP算法[13]進行比較。在這里使用標(biāo)準(zhǔn)化互信息NMI 衡量實驗中社區(qū)劃分的效果。NMI 衡量當(dāng)前算法劃分結(jié)果和官方公布的劃分結(jié)果的相似程度，其范圍為0～1，這個值越大則實驗結(jié)果與官方結(jié)果越接近，算法的效果越好。

式中：N是節(jié)點的數(shù)量；C是指示矩陣；Ci表示在算法A劃分中屬于社區(qū)i的節(jié)點數(shù)；Cij表示在算法A 的結(jié)果中屬于社區(qū)i，同時，在算法B 的結(jié)果中屬于社區(qū)j的節(jié)點數(shù)量；CA(CB）表示應(yīng)用算法A（B）后得到的社區(qū)數(shù)目。圖4 是在Zachary 和Dolphin 網(wǎng)絡(luò)上的實驗結(jié)果。

圖4 單關(guān)系網(wǎng)絡(luò)上的實驗結(jié)果

表1 是在單關(guān)系網(wǎng)絡(luò)上的實驗結(jié)果對比，可以看出本文提出的MLCDM 算法相比于對比算法有較好的劃分效果。

3.2 多關(guān)系網(wǎng)絡(luò)上的實驗

在多關(guān)系網(wǎng)絡(luò)的實驗中使用4 個多關(guān)系的twitter 網(wǎng)絡(luò)：politicsIe、politicsUK、football 和 rugby[14]，這 4 個網(wǎng)絡(luò)都有已知的官方正確社區(qū)劃分。首先從原始的twitter信息中提取出用戶之間的“關(guān)注”“轉(zhuǎn)發(fā)”“提及”三種關(guān)系，然后將三種關(guān)系作為三種類型的邊，用戶作為節(jié)點，建立多關(guān)系網(wǎng)絡(luò)，見表2。

表1 單關(guān)系網(wǎng)絡(luò)上的結(jié)果對比

表2 多關(guān)系網(wǎng)絡(luò)數(shù)據(jù)集

因為5 個數(shù)據(jù)集都是twitter 網(wǎng)絡(luò)，屬于同種網(wǎng)絡(luò)且關(guān)系的類型相同，所以可以使用式（6）在某一個有先驗知識的數(shù)據(jù)集上對不同關(guān)系在社區(qū)發(fā)現(xiàn)中的權(quán)重進行計算，然后在其他數(shù)據(jù)集上利用得到的權(quán)重進行社區(qū)發(fā)現(xiàn)。在politicsIe 上用式（6）計算在twitter 網(wǎng)絡(luò)中不同類型的邊在社區(qū)化分中的權(quán)重。在其他數(shù)據(jù)集上使用MLCDM 算法，其中不同種類的邊的權(quán)重即為在politicsIe上計算的值。通過在politicsIe網(wǎng)絡(luò)上應(yīng)用式（6），得出在twitter 網(wǎng)絡(luò)中“關(guān)注”的權(quán)重為0.42，“轉(zhuǎn)發(fā)”的權(quán)重為0.14，“提及”的權(quán)重為0.23。然后在另外3 個多關(guān)系網(wǎng)絡(luò)上利用MLCDM 進行社區(qū)劃分，通常使用純凈度衡量多關(guān)系網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)結(jié)果。定義官方公布的正確社區(qū)結(jié)構(gòu)為C={C0,C1,C2，…，Ck}，當(dāng)前算法計算得到的社區(qū)結(jié)構(gòu)為

式中：n是網(wǎng)絡(luò)上節(jié)點的總數(shù)目是Ci與Cj的交集。純凈度越高則算法的社區(qū)劃分效果越好。

將本文提出的MLCDM 算法與MultiNetCom 算法[9]、Jiang’s 算法[9]及 NCFCM[15]進行對比，結(jié)果見表 3。

表3 多關(guān)系網(wǎng)絡(luò)上的結(jié)果對比

通過表3 可以看出在多關(guān)系網(wǎng)絡(luò)上進行社區(qū)發(fā)現(xiàn)時，本文提出的MLCDM 算法的純凈度和其他幾種算法相比較高，與官方公布的社區(qū)劃分結(jié)果更接近，劃分效果更好。

4 結(jié) 語

實際的網(wǎng)絡(luò)上通常存在著多種關(guān)系，將所有關(guān)系等同看待或者將原網(wǎng)絡(luò)進行拆分后再進行社區(qū)發(fā)現(xiàn)都會使多關(guān)系信息有所丟失，為了更好地完成多關(guān)系網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)任務(wù)，本文提出基于機器學(xué)習(xí)的多關(guān)系網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法MLCDM。主要貢獻點有綜合考慮多關(guān)系網(wǎng)絡(luò)上的不同類型的邊，定義了計算各種類型的邊在社區(qū)發(fā)現(xiàn)時權(quán)重的方法，設(shè)計了面向社區(qū)發(fā)現(xiàn)的多關(guān)系網(wǎng)絡(luò)數(shù)據(jù)采集策略，用采集到的數(shù)據(jù)對節(jié)點的表示模型進行訓(xùn)練，得到節(jié)點的表示向量，再對其進行聚類以實現(xiàn)社區(qū)發(fā)現(xiàn)。最終實驗結(jié)果表明本文提出的MLCDM 算法和近幾年的幾種算法相比，在單關(guān)系網(wǎng)絡(luò)和多關(guān)系網(wǎng)絡(luò)上都有較好的效果。今后主要研究的問題有兩個：解決當(dāng)多關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)隨時間動態(tài)變化時的社區(qū)發(fā)現(xiàn)問題；改進邊的權(quán)重的計算策略，使得其可以根據(jù)社區(qū)發(fā)現(xiàn)的結(jié)果反饋進行動態(tài)更新。

注：本文通訊作者為周強。