多關(guān)系網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)

李叢正，梁 壘，周 強(qiáng)

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

0 引 言

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

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

1 相關(guān)工作

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

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

圖1 詞嵌入的實(shí)例

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

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

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

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

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

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

圖3 節(jié)點(diǎn)的向量表示的計(jì)算流程

2.1 游走采樣

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

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

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

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

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

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

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

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

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

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

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

2. fori=0 toNdo

3. //以節(jié)點(diǎn)Vi為起點(diǎn)開(kāi)始游走

4. forc=0 toCdo

5. ford=0 toDdo

6. if（d==0）then

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

8. else

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

10. END for

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

12. END for

13. END for

14. return Walk

2.2 計(jì)算每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的向量表示

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

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

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

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

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

2.3 模型優(yōu)化

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

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

2.4 聚 類

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

算法2：MLCDM

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

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

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

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

3 forq=0 toQdo

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

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

6 END For

7 END For

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

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

10 returnR

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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

注：本文通訊作者為周強(qiáng)。