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

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

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

0 引言

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

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

社會網(wǎng)絡(luò)依據(jù)包含的節(jié)點和邊的類型是否相同被劃分為兩類：同質(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)移概率模型的隨機游走算法和skipgram 模型結(jié)合來學(xué)習(xí)異質(zhì)網(wǎng)絡(luò)中節(jié)點向量表示的方法。然而，此方法中轉(zhuǎn)移概率模型的定義大多只考慮網(wǎng)絡(luò)中的基本連接關(guān)系（如節(jié)點間的直接連接關(guān)系），僅僅保持一階鄰近性，無法捕捉全局網(wǎng)絡(luò)結(jié)構(gòu)。針對上述問題，本文主要基于異質(zhì)網(wǎng)絡(luò)的子網(wǎng)絡(luò)——主題關(guān)注網(wǎng)絡(luò)［8-10］進行表示學(xué)習(xí)的相關(guān)研究。如圖1 所示，該網(wǎng)絡(luò)由兩類節(jié)點和邊構(gòu)成，其中，ui和tk分別表示用戶和主題節(jié)點。針對異質(zhì)網(wǎng)絡(luò)中節(jié)點和邊之間結(jié)構(gòu)和語義等各方面的特點，運用集對分析理論中的同異反（確定與不確定）思想，提出了基于主題關(guān)注網(wǎng)絡(luò)的表示學(xué)習(xí)（Topic-Attention Network Embedding，TANE）算法。主要內(nèi)容如下：

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

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

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

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

1 相關(guān)工作

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

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

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

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

主題關(guān)注網(wǎng)絡(luò)［10］被定義為一個二元組G=（V，E），其中：V={U，T}，U={u1，u2，…，un}表示用戶節(jié)點集，T=｛t1，t2，…，tm｝表 示 主 題 節(jié) 點 集；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é)點ui的1 級和2 級鄰居集（包含用戶鄰居集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)定義詳見文獻［10］。該網(wǎng)絡(luò)是融合了社交關(guān)系和興趣愛好的模型，節(jié)點之間的邊具有明顯的語義特征。

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

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

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

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

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

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

3.2.1 相關(guān)定義

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

針對圖2 主題關(guān)注網(wǎng)絡(luò)中兩類節(jié)點間的關(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)表示兩個用戶節(jié)點是否直接相連，如式（2）所示。

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

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

Pij（4）表示兩個用戶節(jié)點通過共同的2 級主題建立連接關(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分別表示兩個用戶節(jié)點通過CN(ui，uj)1建立連接關(guān)系時，兩個節(jié)點共同的用戶和主題所占的權(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é)點和主題節(jié)點是否直接相連，計算方法同式（2）；Pik（2）表示用戶節(jié)點與主題節(jié)點通過CNU（ui，tk）1建立連接關(guān)系，計算方法同式（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é)點和用戶節(jié)點是否直接相連，計算方法同式（2）。

3.2.2 實例

為了更加直觀地理解上述定義，利用圖1 中的(u1，u4)、(u5，t3)、(t3，u5)分別給出上述定義的計算過程。以節(jié)點u1、u4為研究對象，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é)點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é) 點u1到u4的 轉(zhuǎn) 移 概 率 為同 理 可 得(u5，t3)和(t3，u5)的鄰居情況，如表1 所示，計算轉(zhuǎn)移概率分別為

3.3 TANE算法框架

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

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

3.3.1 UT-walk算法

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

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

算法1 UT-walk。

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

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

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

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

算法2 TANE。

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

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

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

4.1 實驗設(shè)置

4.1.1 數(shù)據(jù)集和對比實驗

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

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

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

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

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

4.1.2 評價指標(biāo)

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

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

4.2 結(jié)果與分析

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

4.2.1 基于Karate網(wǎng)絡(luò)的實驗

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

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

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

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

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

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

4.2.2 基于聚類算法的分析

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

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

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

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

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

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

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

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

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

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

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

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

圖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é)語

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

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