郭景峰，董 慧*，張庭瑋，陳 曉

（1.燕山大學(xué)信息科學(xué)與工程學(xué)院，河北秦皇島066004；2.河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室，河北秦皇島066004；3.河北科技師范學(xué)院網(wǎng)絡(luò)技術(shù)中心，河北秦皇島066004）

0 引言

鄰接矩陣作為網(wǎng)絡(luò)最直觀的表現(xiàn)形式，其運(yùn)算的時(shí)間復(fù)雜度和存儲(chǔ)的空間復(fù)雜度均較高，使得很多現(xiàn)有算法無(wú)法應(yīng)用到大規(guī)模網(wǎng)絡(luò)中。針對(duì)大規(guī)模網(wǎng)絡(luò)的分析迫切需要一種合理、高效的網(wǎng)絡(luò)表示方式，因此，網(wǎng)絡(luò)表示學(xué)習(xí)成為近年來(lái)的研究熱點(diǎn)。

網(wǎng)絡(luò)表示學(xué)習(xí)［1］與傳統(tǒng)的基于鄰接矩陣的網(wǎng)絡(luò)分析方法不同，它結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)和語(yǔ)義等特點(diǎn)學(xué)習(xí)網(wǎng)絡(luò)潛在、低維、稠密的嵌入向量空間表示。由于網(wǎng)絡(luò)嵌入向量很容易被機(jī)器學(xué)習(xí)算法處理，因而受到學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注，也有效地運(yùn)用到節(jié)點(diǎn)分類、聚類、鏈接預(yù)測(cè)等任務(wù)中。

社會(huì)網(wǎng)絡(luò)依據(jù)包含的節(jié)點(diǎn)和邊的類型是否相同被劃分為兩類：同質(zhì)網(wǎng)絡(luò)和異質(zhì)網(wǎng)絡(luò)。目前，同質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)方面的方法較多且比較深入；而異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)方面的方法大致分為基于矩陣分解的方法［2］、基于自定義損失函數(shù)的方法［3-4］和基于神經(jīng)網(wǎng)絡(luò)的方法［5-7］三類。其中，基于神經(jīng)網(wǎng)絡(luò)的方法［5］中涉及一種基于轉(zhuǎn)移概率模型的隨機(jī)游走算法和skipgram 模型結(jié)合來(lái)學(xué)習(xí)異質(zhì)網(wǎng)絡(luò)中節(jié)點(diǎn)向量表示的方法。然而，此方法中轉(zhuǎn)移概率模型的定義大多只考慮網(wǎng)絡(luò)中的基本連接關(guān)系（如節(jié)點(diǎn)間的直接連接關(guān)系），僅僅保持一階鄰近性，無(wú)法捕捉全局網(wǎng)絡(luò)結(jié)構(gòu)。針對(duì)上述問(wèn)題，本文主要基于異質(zhì)網(wǎng)絡(luò)的子網(wǎng)絡(luò)——主題關(guān)注網(wǎng)絡(luò)［8-10］進(jìn)行表示學(xué)習(xí)的相關(guān)研究。如圖1 所示，該網(wǎng)絡(luò)由兩類節(jié)點(diǎn)和邊構(gòu)成，其中，ui和tk分別表示用戶和主題節(jié)點(diǎn)。針對(duì)異質(zhì)網(wǎng)絡(luò)中節(jié)點(diǎn)和邊之間結(jié)構(gòu)和語(yǔ)義等各方面的特點(diǎn)，運(yùn)用集對(duì)分析理論中的同異反（確定與不確定）思想，提出了基于主題關(guān)注網(wǎng)絡(luò)的表示學(xué)習(xí)（Topic-Attention Network Embedding，TANE）算法。主要內(nèi)容如下：

1）提出一種基于集對(duì)分析理論構(gòu)建轉(zhuǎn)移概率模型的方法。該模型針對(duì)主題關(guān)注網(wǎng)絡(luò)中4 階［11］范圍內(nèi)兩類節(jié)點(diǎn)（用戶和主題）間連接關(guān)系中的幾種情況，采用集對(duì)分析理論中同異反思想將主題關(guān)注網(wǎng)絡(luò)刻畫為一個(gè)同異反（確定與不確定）系統(tǒng)，構(gòu)建節(jié)點(diǎn)間的轉(zhuǎn)移概率模型。

2）提出一種基于用戶和主題節(jié)點(diǎn)的游走（User Topicwalk，UT-walk）算法。該算法基于用戶到用戶、用戶與主題之間的轉(zhuǎn)移概率給出隨機(jī)游走策略，實(shí)現(xiàn)兩類節(jié)點(diǎn)間靈活的游走，得到游走序列，并通過(guò)訓(xùn)練該序列得到高質(zhì)量的網(wǎng)絡(luò)嵌入向量空間表示。

3）在兩個(gè)數(shù)據(jù)集上對(duì)本文提出的算法進(jìn)行了實(shí)驗(yàn)，利用K-means++聚類算法進(jìn)行社區(qū)發(fā)現(xiàn)，選取模塊度作為評(píng)價(jià)指標(biāo)，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的有效性，聚類結(jié)果計(jì)算出的模塊度相對(duì)較高。

圖1 主題關(guān)注網(wǎng)絡(luò)Fig.1 Topic-attention network

1 相關(guān)工作

隨著社交網(wǎng)絡(luò)用戶的迅速增長(zhǎng)使得傳統(tǒng)的網(wǎng)絡(luò)表示方法遇到瓶頸，結(jié)合深度學(xué)習(xí)的網(wǎng)絡(luò)表示方法逐漸興起。

DeepWalk 算法［12］首次將深度學(xué)習(xí)中的技術(shù)引入到同質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)中，該算法運(yùn)用Word2vec［13］模型的思想將節(jié)點(diǎn)視為單詞、隨機(jī)游走序列視為句子，訓(xùn)練得到網(wǎng)絡(luò)的嵌入向量空間表示，在多標(biāo)簽分類任務(wù)上證明了其有效性。Node2vec算法［14］結(jié)合廣度優(yōu)先遍歷（Breadth First Search，BFS）和深度優(yōu)先遍歷（Depth First Search，DFS）搜索算法，同時(shí)考慮到局部和全局信息，改善了DeepWalk 算法中的隨機(jī)游走策略；LINE（Large-scale Information Network Embedding）算法［15］通過(guò)不直接相連的兩個(gè)節(jié)點(diǎn)的鄰居刻畫二階相似度，對(duì)Deepwalk的一階近鄰稀疏問(wèn)題作了改進(jìn)。Node2vec 和LINE 這兩個(gè)算法較Deepwalk 算法在多標(biāo)簽分類任務(wù)方面的結(jié)果明顯提高。保持Motif 結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)（Motif-Preserving Network Embedding，MPNE）算法［16］結(jié)合Motif 結(jié)構(gòu)進(jìn)行高階的網(wǎng)絡(luò)表示學(xué)習(xí)，在多標(biāo)簽分類任務(wù)上取得了更好的結(jié)果。SDNE（Structural Deep Network Embedding）算法［17］結(jié)合神經(jīng)網(wǎng)絡(luò)模型來(lái)捕捉網(wǎng)絡(luò)中高度非線性的關(guān)系，最終將隱層權(quán)重作為網(wǎng)絡(luò)的嵌入表示，在鏈接預(yù)測(cè)任務(wù)上得到了突出的實(shí)驗(yàn)結(jié)果。

異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)研究從PTE（Predictive Text Embedding）［3］算法逐漸起步，該算法是將predictive 的信息在最后的embedding 體現(xiàn)出來(lái)，但不像卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Network，CNN）或 循 環(huán) 神 經(jīng) 網(wǎng) 絡(luò)（Recurrent Neural Network，RNN）模型直接嵌套一個(gè)復(fù)雜的預(yù)測(cè)模型；PME（Projected Metric Embedding）算法［4］使用度量學(xué)習(xí)方法同時(shí)捕捉網(wǎng)絡(luò)中的一階和二階關(guān)系，在對(duì)象、關(guān)系空間分別學(xué)習(xí)節(jié)點(diǎn)、關(guān)系的向量表示；metapath2vec 和metapath2vec++算法［5］均基于DeepWalk 的思想，利用元路徑指導(dǎo)隨機(jī)游走，并用異質(zhì)的skip-gram 模型進(jìn)行訓(xùn)練得到網(wǎng)絡(luò)的嵌入向量空間表示；HIN2vec 算法［6］結(jié)合神經(jīng)網(wǎng)絡(luò)模型，在得到網(wǎng)絡(luò)的嵌入向量空間表示的同時(shí)還學(xué)到了關(guān)系（元路徑）的表示；DVNE（Deep Variational Network Embedding）算法［7］利用神經(jīng)網(wǎng)絡(luò)模型結(jié)合Wasserstein距離改變了度量?jī)蓚€(gè)分布之間相似性的方法，使其既能滿足三角不等式，又能在無(wú)向圖中很好地保持鄰近性的傳遞性。以上算法在多標(biāo)簽分類、聚類和鏈接預(yù)測(cè)等網(wǎng)絡(luò)分析任務(wù)方面取得了較好的實(shí)驗(yàn)效果。目前，在基于元路徑［18］隨機(jī)游走策略的異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)中帶偏置的隨機(jī)游走方式限制條件較多，因此，有必要針對(duì)異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)探究新的理論和方法。

2 主題關(guān)注網(wǎng)絡(luò)

主題關(guān)注網(wǎng)絡(luò)［10］被定義為一個(gè)二元組G=（V，E），其中：V={U，T}，U={u1，u2，…，un}表示用戶節(jié)點(diǎn)集，T=｛t1，t2，…，tm｝表 示 主 題 節(jié) 點(diǎn) 集；E=｛EUU，EUT｝表 示 邊 集，其 中，EUU={(ui，uj)|ui，uj∈U}表示用戶與用戶間的關(guān)系，EUT=｛（ui，tk）|ui∈U，tk∈T｝表示用戶與主題間的關(guān)系。

在主題關(guān)注網(wǎng)絡(luò)中，N(ui)1=NU(ui)1∪NT(ui)1和N(ui)2=NU(ui)2∪NT(ui)2分別表示節(jié)點(diǎn)ui的1 級(jí)和2 級(jí)鄰居集（包含用戶鄰居集NU(ui)m和主題鄰居集NT(ui)m，m=1，2）；CN(ui，uj)1=CNU(ui，uj)1∪CNT(ui，uj)1和CN(ui，uj)2=分 別 表 示 N(ui)1∩N(uj)1和N(ui)2∩N(uj)2；和CN(ui，uj)2∩1=CNU(ui，uj)2∩1∪CNT(ui，uj)2∩1分 別 表 示N(ui)1∩N(uj)2和N(ui)2∩N(uj)1，其他相關(guān)定義詳見(jiàn)文獻(xiàn)［10］。該網(wǎng)絡(luò)是融合了社交關(guān)系和興趣愛(ài)好的模型，節(jié)點(diǎn)之間的邊具有明顯的語(yǔ)義特征。

3 基于主題關(guān)注網(wǎng)絡(luò)的表示學(xué)習(xí)算法

3.1 基于集對(duì)分析理論的主題關(guān)注網(wǎng)絡(luò)建模

集對(duì)分析理論［19］的核心思想是將事物之間的聯(lián)系看成是一個(gè)系統(tǒng)，簡(jiǎn)稱為同異反（確定與不確定）系統(tǒng)。其中，確定性包含同和反，通常指事物的同一和對(duì)立兩個(gè)方面，在此僅考慮同一方面；不確定性為異，通常指事物宏觀和微觀方面的影響因素。采用該思想構(gòu)建主題關(guān)注網(wǎng)絡(luò)模型的關(guān)鍵即為構(gòu)建節(jié)點(diǎn)間的確定和不確定關(guān)系。

主題關(guān)注網(wǎng)絡(luò)包含用戶和主題兩類節(jié)點(diǎn)，以及用戶-用戶、用戶-主題、主題-用戶三種節(jié)點(diǎn)間關(guān)系，基于該網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，將兩個(gè)用戶節(jié)點(diǎn)通過(guò)與其直接相連的節(jié)點(diǎn)建立的關(guān)系視為確定關(guān)系，如用戶間如果擁有共同的朋友或興趣愛(ài)好更容易成為朋友；將兩個(gè)用戶節(jié)點(diǎn)通過(guò)與其間接相連的節(jié)點(diǎn)建立的關(guān)系視為不確定性關(guān)系，如用戶間分別通過(guò)其朋友分享共同的興趣愛(ài)好成為朋友的不確定性較大，但在一定條件下可轉(zhuǎn)化為確定性關(guān)系。如圖2 所示，將（ui，uj）、（ui，tk）、（tk，ui）三種節(jié)點(diǎn)間二階范圍內(nèi)的連接關(guān)系作為確定部分，其他情況作為不確定部分建模。

圖2 建模涉及的節(jié)點(diǎn)間連接情況Fig.2 Connections between nodes involved in modeling

3.2 轉(zhuǎn)移概率模型

3.2.1 相關(guān)定義

傳統(tǒng)同質(zhì)社會(huì)網(wǎng)絡(luò)中基于轉(zhuǎn)移概率模型進(jìn)行網(wǎng)絡(luò)分析已經(jīng)結(jié)合BFS 和DFS 等方法考慮到節(jié)點(diǎn)2 階范圍內(nèi)的鄰居，但無(wú)法準(zhǔn)確捕捉全局網(wǎng)絡(luò)結(jié)構(gòu)?；诂F(xiàn)實(shí)網(wǎng)絡(luò)的多樣性（如網(wǎng)絡(luò)中包括多種類型的節(jié)點(diǎn)和邊）及網(wǎng)絡(luò)關(guān)系的復(fù)雜性（如朋友間通過(guò)共同的興趣愛(ài)好建立聯(lián)系）在主題關(guān)注網(wǎng)絡(luò)中全面準(zhǔn)確地定義轉(zhuǎn)移概率模型作為研究重點(diǎn)。

針對(duì)圖2 主題關(guān)注網(wǎng)絡(luò)中兩類節(jié)點(diǎn)間的關(guān)系，融合網(wǎng)絡(luò)結(jié)構(gòu)、主題偏好及確定與不確定性思想構(gòu)建轉(zhuǎn)移概率模型，具體定義如下。

定義1用戶到用戶的轉(zhuǎn)移概率。給定主題關(guān)注網(wǎng)絡(luò)G=(V，E)，?ui，uj∈U，tk∈T，考 慮 NU(ui)1、CN(ui，uj)1、CNT(ui，uj)1∩2和CNT(ui，uj)2∩1以及CNT(ui，uj)2，用戶到用戶的轉(zhuǎn)移概率記為P(uj|ui)，如式（1）所示。

其中：Pij(1)表示兩個(gè)用戶節(jié)點(diǎn)是否直接相連，如式（2）所示。

其中：di表示節(jié)點(diǎn)ui的度；S起標(biāo)記作用，S=1表示兩個(gè)節(jié)點(diǎn)間有直接連接關(guān)系，否則S=0。

Pij(2)表示兩個(gè)用戶節(jié)點(diǎn)通過(guò)共同1 級(jí)鄰居建立連接關(guān)系，如式（3）所示。

Pij（4）表示兩個(gè)用戶節(jié)點(diǎn)通過(guò)共同的2 級(jí)主題建立連接關(guān)系，如式（6）所示；

其 中：α、β、γ1、γ2和δ 分 別 表 示CNT(ui，uj)1∩2和CNT（ui，uj）2∩1以及CNT（ui，uj）2所占的權(quán)重系數(shù)，且α+β+γ1+γ2+δ=1；χ1和χ2分別表示兩個(gè)用戶節(jié)點(diǎn)通過(guò)CN(ui，uj)1建立連接關(guān)系時(shí)，兩個(gè)節(jié)點(diǎn)共同的用戶和主題所占的權(quán)重系數(shù)，且χ1+χ2=1。

定義2用戶到主題的轉(zhuǎn)移概率。給定主題關(guān)注網(wǎng)絡(luò)G=（V，E），?ui，up∈U，tk∈T，考慮NT（ui）1、CNU（ui，tk）1，用戶到主題的轉(zhuǎn)移概率記為P(tk|ui)，如式（7）所示。

其中：Pik（1）表示用戶節(jié)點(diǎn)和主題節(jié)點(diǎn)是否直接相連，計(jì)算方法同式（2）；Pik（2）表示用戶節(jié)點(diǎn)與主題節(jié)點(diǎn)通過(guò)CNU（ui，tk）1建立連接關(guān)系，計(jì)算方法同式（3）；ε、θ 分別表示NT（ui）1和CNU（ui，tk）1所占的權(quán)重系數(shù)，且ε+θ=1。

定義3主題到用戶的轉(zhuǎn)移概率。給定主題關(guān)注網(wǎng)絡(luò)G=(V，E)，?ui，uj∈U，tk∈T，考慮NU(tk)1，主題到用戶的轉(zhuǎn)移概率記為P(ui|tk)，如式（8）所示。

其中：Pki（1）表示主題節(jié)點(diǎn)和用戶節(jié)點(diǎn)是否直接相連，計(jì)算方法同式（2）。

3.2.2 實(shí)例

為了更加直觀地理解上述定義，利用圖1 中的(u1，u4)、(u5，t3)、(t3，u5)分別給出上述定義的計(jì)算過(guò)程。以節(jié)點(diǎn)u1、u4為研究對(duì)象，NT(u1)1={t2}，NU(u1)1={u2，u4，u5}，NT(u4)1={t3}，NU(u4)1={u1，u2，u3，u5，u6}。(u1，u4)∈EUU，即S=1；CNT(u1，u4)1=，即|CNT(u1，u4)1|=0，CNU(u1，u4)1={u2，u5}，即|CNU(u1，u4)1|=2；同理，節(jié)點(diǎn)u1和u4的其他鄰居集分別為CNT(u1，u4)1∩2={t2}、CNT(u1，u4)2∩1={t3}和CNT（u1，u4)2={t1}，即 |CNT(u1，u4)1∩2|=1、|CNT(u1，u4)2∩1|=1 和|CNT(u1，u4)2|=1。因 此，節(jié) 點(diǎn)u1到u4的 轉(zhuǎn) 移 概 率 為同 理 可 得(u5，t3)和(t3，u5)的鄰居情況，如表1 所示，計(jì)算轉(zhuǎn)移概率分別為

3.3 TANE算法框架

TANE 算法的核心思想是將上述定義得到的轉(zhuǎn)移概率模型運(yùn)用到隨機(jī)游走算法得到隨機(jī)游走序列，通過(guò)訓(xùn)練該序列，得到兩類節(jié)點(diǎn)的向量表示。根據(jù)不同的需求利用兩類節(jié)點(diǎn)的向量表示，如運(yùn)用網(wǎng)絡(luò)中用戶節(jié)點(diǎn)的向量表示進(jìn)行社區(qū)發(fā)現(xiàn)任務(wù)，或是根據(jù)網(wǎng)絡(luò)中主題節(jié)點(diǎn)的分布情況對(duì)社區(qū)內(nèi)用戶進(jìn)行合理化推薦等。

表1 節(jié)點(diǎn)對(duì)間的鄰居數(shù)量Tab.1 Number of neighbors between node pairs

3.3.1 UT-walk算法

基于上述三種轉(zhuǎn)移概率模型，提出了基于主題關(guān)注網(wǎng)絡(luò)的隨機(jī)游走算法，如算法1 所示。在算法1 中，第1）行表示初始化隨機(jī)游走路徑；第2）行表示起始節(jié)點(diǎn)的選取是隨機(jī)的，可為用戶或主題節(jié)點(diǎn)；第3）～5）行分別表示在游走路徑長(zhǎng)度L范圍內(nèi)對(duì)當(dāng)前節(jié)點(diǎn)（vcurrent）的選取、計(jì)算給定vcurrent的前提下轉(zhuǎn)移到下一個(gè)節(jié)點(diǎn)的轉(zhuǎn)移概率以及下一個(gè)節(jié)點(diǎn)的選取方法。

在主題關(guān)注網(wǎng)絡(luò)中，結(jié)合轉(zhuǎn)移概率模型選取下一個(gè)節(jié)點(diǎn)主要有兩種策略：1）若vcurrent是用戶節(jié)點(diǎn)，則vnext是用戶或主題節(jié)點(diǎn)；2）若vcurrent是主題節(jié)點(diǎn)，則vnext一定為用戶節(jié)點(diǎn)。vnext的選取通過(guò)帶權(quán)重（即轉(zhuǎn)移概率）的非均勻采樣實(shí)現(xiàn)，更傾向于轉(zhuǎn)移概率大（與vcurrent共同用戶和主題數(shù)量多）的節(jié)點(diǎn)。

算法1 UT-walk。

輸入 G=（V，E），隨機(jī)給定一個(gè)起始節(jié)點(diǎn)u，路徑長(zhǎng)度L，轉(zhuǎn)移概率P；

輸出 包含兩類節(jié)點(diǎn)的隨機(jī)游走序列。

以圖1 中u1和t3為例說(shuō)明上述算法，轉(zhuǎn)移概率模型的參數(shù)設(shè)置與表7中Karate 一致，與其他節(jié)點(diǎn)的轉(zhuǎn)移概率如表2所示。由表2可知，如果以u(píng)1作為當(dāng)前節(jié)點(diǎn)vcurrent，則下一個(gè)節(jié)點(diǎn)vnext的選取更傾向于u2、u4、t1、t2轉(zhuǎn)移概率相對(duì)較大的節(jié)點(diǎn)。由P（u5∣u1）＜P（u6∣u1）看出，節(jié)點(diǎn)間轉(zhuǎn)移概率大不是因?yàn)楣?jié)點(diǎn)間存在直接連接關(guān)系，還有可能是間接連接關(guān)系豐富。綜上，隨機(jī)游走下一個(gè)節(jié)點(diǎn)vnext的選取要考慮節(jié)點(diǎn)的間接連接關(guān)系。

表2 分別以節(jié)點(diǎn)u1和t3作為vcurrent的轉(zhuǎn)移概率Tab.2 Transition probability with node u1 and t3 as vcurrent

3.3.2 TANE算法

主題關(guān)注網(wǎng)絡(luò)表示學(xué)習(xí)（TANE）算法結(jié)合了轉(zhuǎn)移概率模型和UT-walk 算法，如算法2 所示。在算法2 中，第1）行表示初始化隨機(jī)游走路徑集合；第2）～8）行分別表示在每個(gè)節(jié)點(diǎn)作為起始節(jié)點(diǎn)次數(shù)n 的前提下，通過(guò)UT-walk 算法對(duì)起始節(jié)點(diǎn)、游走路徑長(zhǎng)度等參數(shù)進(jìn)行設(shè)置，運(yùn)用轉(zhuǎn)移概率模型得到多條相對(duì)高質(zhì)量的隨機(jī)游走序列；第9）行使用Word2vec模型對(duì)隨機(jī)游走序列進(jìn)行訓(xùn)練，得到主題關(guān)注網(wǎng)絡(luò)的嵌入向量空間Φ。

算法2 TANE。

輸入 G=（V，E），上下文窗口大小w，每個(gè)節(jié)點(diǎn)作為起始節(jié)點(diǎn)的次數(shù)n，生成的向量空間維度d，路徑長(zhǎng)度L，轉(zhuǎn)移概率P；

輸出 節(jié)點(diǎn)的向量空間表示矩陣Φ ∈R∣V∣×d。

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

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 數(shù)據(jù)集和對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)選取了兩個(gè)基準(zhǔn)數(shù)據(jù)集和五個(gè)經(jīng)典算法，具體介紹如下。

1）Zachary’s Karate club數(shù)據(jù)集是社交網(wǎng)絡(luò)分析領(lǐng)域中的經(jīng)典數(shù)據(jù)集，由34個(gè)節(jié)點(diǎn)和78條邊組成。

2）豆瓣數(shù)據(jù)集是一個(gè)通過(guò)爬蟲(chóng)程序抓取的包含用戶間的關(guān)注屬性和電影評(píng)論屬性兩部分信息的網(wǎng)絡(luò)。對(duì)數(shù)據(jù)集進(jìn)行處理，過(guò)濾掉用戶對(duì)電影評(píng)分在3 分以下的信息，最終網(wǎng)絡(luò)中有2 289 個(gè)節(jié)點(diǎn)（2 253 個(gè)用戶+36 個(gè)主題）和70 489 條邊（34 580 條用戶與用戶之間的邊+35 909 條用戶與主題之間的邊）。

5 個(gè)經(jīng)典算法分別為：DeepWalk、Node2vec、MPNE、PTE和metapath2vec。為了使實(shí)驗(yàn)結(jié)果更有說(shuō)服力，對(duì)比算法中的參數(shù)均與原論文一致，維度設(shè)置如表3所示。

表3 各算法的向量維度設(shè)置Tab.3 Vector dimension settings of different algorithms

4.1.2 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)選擇節(jié)點(diǎn)聚類作為網(wǎng)絡(luò)分析任務(wù)，選取模塊度（Modularity，Q）作為評(píng)價(jià)指標(biāo)，如式（9）所示，Q ∈[-1/2，1)，Q越大，則表明社區(qū)劃分質(zhì)量越好。

需要說(shuō)明的是，該實(shí)驗(yàn)是為了證明主題節(jié)點(diǎn)對(duì)社交關(guān)系穩(wěn)定的重要性，主題僅起橋梁的作用，聚類分析以及計(jì)算Q時(shí)去掉網(wǎng)絡(luò)中的主題節(jié)點(diǎn)。

4.2 結(jié)果與分析

實(shí)驗(yàn)主要分為三部分：1）驗(yàn)證主題對(duì)轉(zhuǎn)移概率和向量表示的影響；2）驗(yàn)證TANE 算法的正確性和合理性；3）參數(shù)敏感性分析。

4.2.1 基于Karate網(wǎng)絡(luò)的實(shí)驗(yàn)

Karate 網(wǎng)絡(luò)是一個(gè)無(wú)主題的真實(shí)網(wǎng)絡(luò)，針對(duì)該網(wǎng)絡(luò)（如圖3（a）所示）及對(duì)其添加主題（如圖3（b）所示）兩種情況進(jìn)行比較，以分析主題對(duì)網(wǎng)絡(luò)表示學(xué)習(xí)的影響。

圖3 Karate網(wǎng)絡(luò)示意圖Fig.3 Schematic diagram of Karate network

運(yùn)用DeepWalk算法和TANE算法得到Karate網(wǎng)絡(luò)的兩種嵌入向量空間表示，通過(guò)計(jì)算節(jié)點(diǎn)間向量表示的歐氏距離展開(kāi)分析。由于考慮4階范圍內(nèi)節(jié)點(diǎn)間的關(guān)系，Karate網(wǎng)絡(luò)較稠密，4階鄰居僅僅涉及1個(gè)節(jié)點(diǎn)，因此，圖4（a）、（b）、（c）分別展示兩個(gè)算法下34 個(gè)節(jié)點(diǎn)與每個(gè)節(jié)點(diǎn)一階、二階和三階鄰居間向量表示的歐氏距離變化趨勢(shì)。

從圖4 中可以看出，三種情況下歐氏距離變化趨勢(shì)基本一致。由于轉(zhuǎn)移概率模型定義時(shí)考慮的范圍不同，使得Karate 網(wǎng)絡(luò)中整體節(jié)點(diǎn)間向量表示的歐氏距離減小了，有些節(jié)點(diǎn)間向量表示的距離的波動(dòng)情況相比DeepWalk 算法產(chǎn)生了偏差。為了分析產(chǎn)生偏差的原因，以一階鄰居較多的u1、u34節(jié)點(diǎn)和容易出現(xiàn)分歧的u3、u10節(jié)點(diǎn)為例，將圖中部分區(qū)域放大，如圖5所示。vnext的選取通過(guò)帶權(quán)重（即轉(zhuǎn)移概率）的非均勻采樣實(shí)現(xiàn)，節(jié)點(diǎn)間轉(zhuǎn)移概率越接近，得到節(jié)點(diǎn)的向量表示越相似，節(jié)點(diǎn)間向量表示的距離越小，圖中折線的波動(dòng)情況反映了此現(xiàn)象。圖5 中用加粗線標(biāo)記波動(dòng)比較明顯的情況，以圖5（a）中加粗線標(biāo)記為例詳細(xì)分析原因。TANE算法中，u1到標(biāo)記范圍內(nèi)節(jié)點(diǎn)的轉(zhuǎn)移概率如表4 所示，從表中可以看出，P（u1∣u10）最小，其他情況的轉(zhuǎn)移概率相差不大，從而dist（u1，u10）最大，即u10與x軸間的垂直距離最大，所以，虛線標(biāo)記的折線段除u10處波動(dòng)明顯外其余節(jié)點(diǎn)相對(duì)平穩(wěn)；而DeepWalk 算法中，轉(zhuǎn)移概率模型定義僅考慮了一階鄰居，無(wú)法根據(jù)轉(zhuǎn)移概率對(duì)間接連接關(guān)系進(jìn)行詳細(xì)分析。綜上分析，TANE 算法符合網(wǎng)絡(luò)表示學(xué)習(xí)的核心思想。

圖4 在兩種算法下各階鄰居間歐氏距離的比較Fig.4 Comparison of Euclidean distance between neighbors in two algorithms

圖5 在兩種算法下4個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)間歐氏距離的比較Fig.5 Comparison of Euclidean distance between four nodes and other nodes in two algorithms

4.2.2 基于聚類算法的分析

經(jīng)過(guò)上述分析，在豆瓣網(wǎng)絡(luò)上采用K-means++算法完成聚類分析任務(wù)。經(jīng)過(guò)比較，選取肘部法則確定聚類簇?cái)?shù)K，其核心指標(biāo)是誤差平方和（Sum of the Squared Errors，SSE），如式（10）所示；核心思想是隨著聚類簇?cái)?shù)K 的增大，SSE 值會(huì)逐漸減小并趨于平緩，拐點(diǎn)對(duì)應(yīng)的K 值就是數(shù)據(jù)的真實(shí)聚類簇?cái)?shù)。

首先，運(yùn)用肘部法則確定Karate 網(wǎng)絡(luò)的K 值，如圖6（a）所示，拐點(diǎn)為4，與DeepWalk 論文中運(yùn)用Modularity 算法聚成4類時(shí)Q值達(dá)到最大一致。因此，該方法具有一定的合理性。

表4 u1與圖5（a）中加粗線段范圍內(nèi)節(jié)點(diǎn)間的轉(zhuǎn)移概率Tab.4 Transition probability between u1 and nodes in the range of bold line segment in Fig.5（a）

然后，運(yùn)用肘部法則確定豆瓣網(wǎng)絡(luò)的K 值，如圖6（b）所示，為了實(shí)驗(yàn)的準(zhǔn)確性，K 在拐點(diǎn)范圍內(nèi)取值，即K∈［5，13］。初始聚類中心的選擇具有隨機(jī)性，結(jié)果有小幅度變化，針對(duì)每個(gè)K值做了15次實(shí)驗(yàn)，取平均值作為最終結(jié)果。如表5所示，在K的取值范圍內(nèi)，TANE算法都取得了較好的結(jié)果。

綜上，TANE 算法劃分社區(qū)結(jié)構(gòu)考慮了網(wǎng)絡(luò)的結(jié)構(gòu)和語(yǔ)義等方面的信息，具有實(shí)際應(yīng)用價(jià)值，如在推薦系統(tǒng)中進(jìn)行合理化、個(gè)性化推薦。

圖6 用肘部法則分別確定Karate和豆瓣網(wǎng)絡(luò)的聚類簇?cái)?shù)Fig.6 Numbers of clusters of Karate and Douban networks determined by elbow rule

表5 豆瓣數(shù)據(jù)集上各算法獲得的Q值對(duì)比Tab.5 Comparison of Q values on Douban dataset by different algorithms

4.3 參數(shù)敏感性分析

TANE 算法中涉及到多個(gè)參數(shù)。首先，對(duì)轉(zhuǎn)移概率中的參數(shù)設(shè)置分5 種情況進(jìn)行分析，如表6 所示：第4、5 組參數(shù)設(shè)置得到的Q值相對(duì)較小，因?yàn)榫W(wǎng)絡(luò)中主題節(jié)點(diǎn)稀疏，在很大程度上考慮主題節(jié)點(diǎn)建立的聯(lián)系嚴(yán)重影響提取網(wǎng)絡(luò)中的信息；第1、2、3組參數(shù)設(shè)置得到的Q值相對(duì)較大，由Q2＞Q1，Q1＞Q3可以看出，在權(quán)衡各部分權(quán)重的前提下，基于兩類節(jié)點(diǎn)間的關(guān)系進(jìn)行建模有利于網(wǎng)絡(luò)表示學(xué)習(xí)。最終兩個(gè)數(shù)據(jù)集轉(zhuǎn)移概率模型中的參數(shù)設(shè)置如表7 所示，兩個(gè)數(shù)據(jù)集數(shù)據(jù)量不同，參數(shù)設(shè)置略有差異。

表6 轉(zhuǎn)移概率模型參數(shù)分析Tab.6 Parameters analysis of transition probability model

其次，選用豆瓣數(shù)據(jù)集對(duì)Word2vec 模型中涉及幾個(gè)參數(shù)進(jìn)行分析。如圖7 所示，Word2vec 模型中的有些參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響不大，當(dāng)向量維度d 取64、上下文窗口ω 取5 時(shí)，TANE 算法的表現(xiàn)較好。網(wǎng)絡(luò)中節(jié)點(diǎn)作為起始節(jié)點(diǎn)的次數(shù)n、路徑長(zhǎng)度L 對(duì)實(shí)驗(yàn)結(jié)果影響較明顯，尤其是參數(shù)L，當(dāng)L＞40時(shí)，Q值處于下降趨勢(shì)，算法性能下降。

綜上，TANE 算法中轉(zhuǎn)移概率模型參數(shù)選取時(shí)根據(jù)網(wǎng)絡(luò)中兩類節(jié)點(diǎn)的稀疏情況來(lái)權(quán)衡建模時(shí)各部分的占比；Word2vec 模型中參數(shù)選取時(shí)結(jié)合復(fù)雜度和算法性能兩方面來(lái)考慮。

圖7 Word2vec模型參數(shù)敏感性分析Fig.7 Parameters sensitivity analysis of Word2vec model

表7 轉(zhuǎn)移概率模型參數(shù)設(shè)置Tab.7 Parameters setting of transition probability model

5 結(jié)語(yǔ)

采用集對(duì)分析理論中確定與不確定思想，給出轉(zhuǎn)移概率模型，并將其運(yùn)用到隨機(jī)游走算法，得到了相對(duì)高質(zhì)量的隨機(jī)游走序列；再對(duì)游走序列進(jìn)行訓(xùn)練，得到了主題關(guān)注網(wǎng)絡(luò)的嵌入向量空間表示。實(shí)驗(yàn)結(jié)果表明，在豆瓣數(shù)據(jù)集上與5 個(gè)經(jīng)典算法相比，當(dāng)劃分社區(qū)個(gè)數(shù)為5～13 時(shí)，TANE 算法得到的Q值均有不同幅度的提高，但數(shù)據(jù)集的稀疏性使得Q 值變化并不十分明顯；當(dāng)豆瓣數(shù)據(jù)集上K=13 時(shí)，TANE 算法較metapath2vec 算法的Q 值提高了近5%。綜上，從結(jié)構(gòu)和語(yǔ)義方面分析網(wǎng)絡(luò)，可以更全面地捕捉網(wǎng)絡(luò)中的信息，綜合合理性以及實(shí)驗(yàn)結(jié)果來(lái)考慮，本文提出的TANE 算法取得了較好的表現(xiàn)。

接下來(lái)，在TANE 算法思想的基礎(chǔ)上增大數(shù)據(jù)規(guī)?？紤]異質(zhì)網(wǎng)絡(luò)的動(dòng)態(tài)性和復(fù)雜性進(jìn)行表示學(xué)習(xí)的相關(guān)研究是我們進(jìn)一步的工作重點(diǎn)。