石立鵬,王 莉

(太原理工大學(xué) a.信息與計(jì)算機(jī)學(xué)院; b.大數(shù)據(jù)學(xué)院,山西 晉中 030600)

0 概述

網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展,使社交網(wǎng)絡(luò)成為覆蓋用戶最廣、傳播影響力最大的互聯(lián)網(wǎng)發(fā)展產(chǎn)物之一,其蘊(yùn)含著巨大的商業(yè)價(jià)值。

社交網(wǎng)絡(luò)的主體是網(wǎng)絡(luò)中的用戶,也即網(wǎng)絡(luò)中的節(jié)點(diǎn)。網(wǎng)絡(luò)規(guī)模的不斷壯大對(duì)社交網(wǎng)絡(luò)表征算法提出了新的挑戰(zhàn)。如何對(duì)社交網(wǎng)絡(luò)進(jìn)行準(zhǔn)確、高效地表征,成為一個(gè)重要的研究方向。一個(gè)性能良好的表征算法便于計(jì)算用戶間的相似度、實(shí)現(xiàn)用戶間的鏈預(yù)測(cè)和用戶社區(qū)劃分等。傳統(tǒng)社交網(wǎng)絡(luò)表征算法多數(shù)通過人為特征定義、特征提取、矩陣運(yùn)算以進(jìn)行用戶向量表示。但隨著網(wǎng)絡(luò)節(jié)點(diǎn)(社交網(wǎng)絡(luò)用戶)數(shù)量的增加,傳統(tǒng)方法在準(zhǔn)確率和效率上表現(xiàn)出一定的不足。

近年來(lái),無(wú)監(jiān)督算法在很多研究領(lǐng)域取得了很好的效果。在自然語(yǔ)言處理方面,word2vec模型被提出。受該模型的啟發(fā),在網(wǎng)絡(luò)學(xué)習(xí)中,出現(xiàn)了DeepWalk、Line、node2vec及ComEmbed[1]網(wǎng)絡(luò)表征算法。這些算法能夠避免傳統(tǒng)方法中人為提取特征和大量矩陣運(yùn)算的問題,但都只利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),并未涉及網(wǎng)絡(luò)的交互信息。而用戶間的交互行為恰是社交網(wǎng)絡(luò)的重要組成部分,交互信息對(duì)網(wǎng)絡(luò)表征具有十分積極的作用。

針對(duì)上述算法存在的不足,在現(xiàn)有網(wǎng)絡(luò)表征算法和word2vec模型的基礎(chǔ)上,本文依據(jù)社交網(wǎng)絡(luò)特性,提出一種改進(jìn)的基于遍歷約束與交互信息的網(wǎng)絡(luò)表征算法。該算法分析社交網(wǎng)絡(luò)單個(gè)節(jié)點(diǎn)的特征,通過增加遍歷規(guī)則來(lái)提高學(xué)習(xí)效率,利用網(wǎng)絡(luò)用戶間的交互信息改進(jìn)自然語(yǔ)言模型word2vec,以提高結(jié)果準(zhǔn)確率。

1 相關(guān)工作

1.1 自然語(yǔ)言處理模型

文獻(xiàn)[2]提出word2vec模型后,文獻(xiàn)[3-4]對(duì)單詞表征算法進(jìn)行了改進(jìn),利用單個(gè)單詞與其上下文的關(guān)系,將大量句子集合為語(yǔ)料庫(kù),通過對(duì)語(yǔ)料庫(kù)進(jìn)行訓(xùn)練并使用三層神經(jīng)網(wǎng)絡(luò)對(duì)詞構(gòu)造矢量表征,然后把單詞映射到低維向量空間。雖然文獻(xiàn)[5]指出單詞的向量表征缺乏解釋性,但該模型在自然語(yǔ)言處理中已經(jīng)取得了很好的效果。

1.2 網(wǎng)絡(luò)表征算法

網(wǎng)絡(luò)表征問題一直受到許多研究者的關(guān)注,現(xiàn)有特征表示方法主要有:

1)傳統(tǒng)的譜方法:文獻(xiàn)[6-9]將網(wǎng)絡(luò)轉(zhuǎn)換成矩陣,分別利用鄰接矩陣和拉普拉斯矩陣,通過矩陣運(yùn)算、特征分解、降維等方法得到網(wǎng)絡(luò)表征。但這種方法對(duì)較大型的網(wǎng)絡(luò)并不適用,隨著網(wǎng)絡(luò)中節(jié)點(diǎn)和關(guān)系數(shù)目的增加,矩陣計(jì)算將耗費(fèi)大量時(shí)間及計(jì)算機(jī)資源,且最終得到的向量表示也并不理想。

2)利用自然語(yǔ)言模型的方法:受自然語(yǔ)言處理模型的影響,近年來(lái),很多研究者將網(wǎng)絡(luò)與自然語(yǔ)言模型相結(jié)合,提出很多網(wǎng)絡(luò)表征算法。文獻(xiàn)[10]在DeepWalk中通過網(wǎng)絡(luò)隨機(jī)游走產(chǎn)生節(jié)點(diǎn)序列,類似自然語(yǔ)言中的句子,從而利用自然語(yǔ)言處理模型學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)的特征表示。文獻(xiàn)[11]將深度優(yōu)先遍歷策略和廣度優(yōu)先遍歷策略相結(jié)合,對(duì)語(yǔ)料庫(kù)進(jìn)行優(yōu)化。文獻(xiàn)[12]提出node2vec模型,采用帶有偏置的隨機(jī)游走策略進(jìn)一步提高網(wǎng)絡(luò)表征的準(zhǔn)確性。與傳統(tǒng)的網(wǎng)絡(luò)表征算法相比,這些算法利用機(jī)器學(xué)習(xí)的設(shè)計(jì)思想,在降低計(jì)算復(fù)雜度的同時(shí)能取得較好的網(wǎng)絡(luò)表征效果。

在自然語(yǔ)言中,句子是滿足特定語(yǔ)法規(guī)則的,單詞間的關(guān)系是線性的,每個(gè)單詞都存在特定的上下文。文獻(xiàn)[13]認(rèn)為,網(wǎng)絡(luò)的結(jié)構(gòu)是非線性的,通過不同的遍歷方式產(chǎn)生的序列直接影響網(wǎng)絡(luò)節(jié)點(diǎn)表征的結(jié)果。較普遍的遍歷策略有深度優(yōu)先、廣度優(yōu)先和隨機(jī)遍歷,不同遍歷策略對(duì)結(jié)果會(huì)產(chǎn)生不同的影響,但目前仍然缺少普適性的遍歷策略來(lái)提高網(wǎng)絡(luò)表征的準(zhǔn)確性。

1.3 社交網(wǎng)絡(luò)表征

對(duì)于社交網(wǎng)絡(luò),文獻(xiàn)[14-15]針對(duì)用戶行為以及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征,對(duì)網(wǎng)絡(luò)用戶進(jìn)行矢量化表示。文獻(xiàn)[16]通過用戶興趣和拓?fù)浣Y(jié)構(gòu)實(shí)現(xiàn)社交網(wǎng)絡(luò)的好友推薦。文獻(xiàn)[17]基于社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),利用網(wǎng)絡(luò)的連通性進(jìn)行網(wǎng)絡(luò)用戶表征,最終實(shí)現(xiàn)好友推薦。文獻(xiàn)[18]結(jié)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和用戶信息對(duì)網(wǎng)絡(luò)用戶進(jìn)行表征。這些方法都基于大量的矩陣運(yùn)算,并不適合表征大型社交網(wǎng)絡(luò)。

在利用自然語(yǔ)言模型對(duì)社交網(wǎng)絡(luò)進(jìn)行表征時(shí),文獻(xiàn)[19]將節(jié)點(diǎn)信息加入網(wǎng)絡(luò)表征,可以減少矩陣運(yùn)算,但其表征效果并沒有得到明顯提高。

現(xiàn)有表征算法只考慮網(wǎng)絡(luò)本身,并未有效利用社交網(wǎng)絡(luò)交互信息。而對(duì)于社交網(wǎng)絡(luò),其本質(zhì)是一個(gè)用戶交互平臺(tái),因此,網(wǎng)絡(luò)交互信息對(duì)表征起著重要作用。本文根據(jù)社交網(wǎng)絡(luò)鄰居數(shù)量來(lái)約束網(wǎng)絡(luò)遍歷,同時(shí)利用網(wǎng)絡(luò)交互信息對(duì)網(wǎng)絡(luò)表征的學(xué)習(xí)過程進(jìn)行優(yōu)化。

2 改進(jìn)的社交網(wǎng)絡(luò)表征算法

2.1 網(wǎng)絡(luò)表征學(xué)習(xí)模型

機(jī)器學(xué)習(xí)定義目標(biāo)函數(shù)f,利用合適的優(yōu)化策略對(duì)函數(shù)進(jìn)行優(yōu)化,以得到較好的結(jié)果。對(duì)于網(wǎng)絡(luò)表征算法,一般采用對(duì)數(shù)似然函數(shù)。設(shè)f(w)為節(jié)點(diǎn)w的向量表示,Ns(w)為遍歷策略s下w的鄰居。式(1)為網(wǎng)絡(luò)表征的優(yōu)化目標(biāo):通過遍歷過程中的鄰居節(jié)點(diǎn)以最大化網(wǎng)絡(luò)節(jié)點(diǎn)w的對(duì)數(shù)概率。

(1)

從G中各頂點(diǎn)開始,根據(jù)給定的遍歷策略s生成語(yǔ)料庫(kù),將遍歷序列作為自然語(yǔ)言中的“句子”,序列中各節(jié)點(diǎn)類比自然語(yǔ)言中的“單詞”,根據(jù)節(jié)點(diǎn)出現(xiàn)頻率構(gòu)建Huffman樹,G中節(jié)點(diǎn)作為葉子,非葉子節(jié)點(diǎn)θ作為需要優(yōu)化的參數(shù)。從根到葉子的路徑為多次二分類,利用Huffman編碼可以得到由0和1構(gòu)成的序列h,將該序列與路徑上的二分類結(jié)果對(duì)應(yīng)。對(duì)于節(jié)點(diǎn)w,根據(jù)其當(dāng)前遍歷序列求鄰居節(jié)點(diǎn)向量的和xw。每次分類均對(duì)應(yīng)一次邏輯回歸,其編碼為1或0的概率分別按照式(2)、式(3)計(jì)算:

(2)

(3)

則從根到葉子節(jié)點(diǎn)w的路徑選擇概率對(duì)應(yīng)多次二分類的概率乘積:

(4)

其中,hjw表示節(jié)點(diǎn)w的Huffman編碼中的第j位,lw表示w的Huffman編碼長(zhǎng)度,θjw為該路徑中非葉子節(jié)點(diǎn)的向量表示。最終的優(yōu)化函數(shù)為:

(5)

根據(jù)遍歷序列,采用隨機(jī)梯度上升方法對(duì)參數(shù)θ及節(jié)點(diǎn)w的鄰居進(jìn)行優(yōu)化,并更新各向量。

2.2 基于網(wǎng)絡(luò)結(jié)構(gòu)的遍歷優(yōu)化

在通常情況下,為獲得足夠大的語(yǔ)料庫(kù),可從網(wǎng)絡(luò)中各節(jié)點(diǎn)起始,進(jìn)行相同次數(shù)的遍歷,產(chǎn)生龐大的語(yǔ)料庫(kù)后進(jìn)行訓(xùn)練。然而,通過對(duì)BlogCatalog和新浪微博數(shù)據(jù)集中節(jié)點(diǎn)度的統(tǒng)計(jì),按照好友關(guān)系數(shù)可以得到一條遞減的曲線。在曲線的頭部,由于社交網(wǎng)絡(luò)中名人和粉絲量巨大博主的存在,其好友關(guān)系數(shù)較多,隨著博主影響力的降低,曲線會(huì)顯著下降,尾部曲線會(huì)貼近于橫軸,社交網(wǎng)絡(luò)節(jié)點(diǎn)好友關(guān)系符合長(zhǎng)尾分布。在采用相同遍歷策略產(chǎn)生語(yǔ)料庫(kù)的同時(shí),會(huì)加入大量重復(fù)的句子,這不僅使遍歷時(shí)間加長(zhǎng),增加訓(xùn)練時(shí)間成本,而且不能提高最終的表達(dá)效果,因此,根據(jù)節(jié)點(diǎn)分布約束遍歷次數(shù),更符合社交網(wǎng)絡(luò)的特點(diǎn)。

如圖1所示,與節(jié)點(diǎn)x3關(guān)聯(lián)的只有節(jié)點(diǎn)v,在以節(jié)點(diǎn)x3為起始節(jié)點(diǎn)的遍歷序列中,前兩跳總是固定的(x3,v,…)。而在以節(jié)點(diǎn)v為起始節(jié)點(diǎn)的遍歷序列中,遍歷序列的第2跳可以看作是以x3為起始節(jié)點(diǎn)的第3跳。根據(jù)節(jié)點(diǎn)特征的優(yōu)化算法,以x3為起始點(diǎn)的多次遍歷顯然是沒有必要的。

圖1 節(jié)點(diǎn)遍歷約束示意圖

按照長(zhǎng)尾分布,將所有節(jié)點(diǎn)平均度數(shù)作為“頭”和“尾”的分割。對(duì)于“頭”中的節(jié)點(diǎn),其好友關(guān)系復(fù)雜,根據(jù)算法給出的最大游走次數(shù)遍歷生成語(yǔ)料庫(kù),對(duì)于“尾”中的節(jié)點(diǎn),根據(jù)節(jié)點(diǎn)與均值的比值約束游走次數(shù)。各節(jié)點(diǎn)游走次數(shù)計(jì)算如下:

(6)

其中,vi代表網(wǎng)絡(luò)中的第i個(gè)節(jié)點(diǎn),deg(vi)表示節(jié)點(diǎn)vi的度數(shù),walknum為最大游走次數(shù),avg為所有節(jié)點(diǎn)的平均度數(shù),count(vi)計(jì)算節(jié)點(diǎn)vi的遍歷次數(shù),并作為遍歷約束條件。

本文算法只限制以該節(jié)點(diǎn)為起點(diǎn)的隨機(jī)游走次數(shù),該節(jié)點(diǎn)仍然會(huì)在其他節(jié)點(diǎn)的隨機(jī)游走序列中出現(xiàn)。根據(jù)word2vec原理,對(duì)于度數(shù)較低的點(diǎn),其向量表示同樣可以根據(jù)包含該節(jié)點(diǎn)的其他游走序列進(jìn)行優(yōu)化。

2.3 基于交互行為的算法改進(jìn)

網(wǎng)絡(luò)表征算法及word2vec模型的目的是使相似節(jié)點(diǎn)或單詞具有更加接近的特征表示。在word2vec模型中,單詞初始化向量是隨機(jī)的,向量表示的距離也是隨機(jī)的,但通過大量的語(yǔ)料訓(xùn)練可使具有相似含義的單詞更加接近。這是因?yàn)樽匀徽Z(yǔ)言中的句子是線性的,可以通過大量的訓(xùn)練得到較準(zhǔn)確的表達(dá)?，F(xiàn)有網(wǎng)絡(luò)表征算法大都聚焦于調(diào)整網(wǎng)絡(luò)遍歷策略,然后直接利用word2vec模型得到節(jié)點(diǎn)表征。由于網(wǎng)絡(luò)的非線性特性,當(dāng)網(wǎng)絡(luò)表征準(zhǔn)確率趨于穩(wěn)定后,通過擴(kuò)充訓(xùn)練集來(lái)提高算法表征效果將變得十分困難。

社交網(wǎng)絡(luò)作為用戶交互平臺(tái),存在大量的用戶交互信息,這些信息對(duì)社交網(wǎng)絡(luò)表征具有積極的意義。通過對(duì)社交網(wǎng)絡(luò)的分析發(fā)現(xiàn),用戶在一段時(shí)間內(nèi)存在交互行為的好友,極有可能屬于同一個(gè)或有限幾個(gè)社交圈。因此,可以根據(jù)社交網(wǎng)絡(luò)的這一特點(diǎn)對(duì)word2vec模型進(jìn)行改進(jìn),雖然這無(wú)法完全避免由網(wǎng)絡(luò)非線性結(jié)構(gòu)帶來(lái)的困擾,但卻可以使模型更適合社交平臺(tái)。

在word2vec中,各維向量缺乏解釋性[5],雖然向量中的某些維度可能反映著不同信息,比如在詞向量中,某些維度可能包含了性別這類信息,但現(xiàn)有模型無(wú)法準(zhǔn)確指出每一維向量的具體意義,這也使得該模型在自然語(yǔ)言處理中存在一定的缺陷。然而,對(duì)網(wǎng)絡(luò)表征而言,可以利用這部分信息與網(wǎng)絡(luò)交互集合來(lái)修改word2vec模型的初始化階段,使不同集合間的差異性更突出,然后通過訓(xùn)練使整個(gè)網(wǎng)絡(luò)表征更準(zhǔn)確。

2.3.1 交互集合選擇

社交網(wǎng)絡(luò)用戶的交互行為很頻繁,多數(shù)用戶都會(huì)存在數(shù)量不等的交互信息。為避免平均化,應(yīng)選擇交互量較大用戶的交互好友作為單個(gè)優(yōu)化集合,選擇交集較小的不同用戶的交互集合作為優(yōu)化對(duì)象。

交互集合作為算法優(yōu)化的依據(jù),需滿足如下條件:1)應(yīng)選擇交互關(guān)系數(shù)較大的多個(gè)用戶的交互集合,以減少集合個(gè)數(shù),同時(shí)避免優(yōu)化結(jié)果的平均化;2)單個(gè)交互集合內(nèi)元素與同一用戶存在交互行為;3)不同交互集合的交集盡可能小,避免對(duì)同一用戶進(jìn)行多次優(yōu)化從而降低區(qū)分度。

2.3.2 表征算法優(yōu)化

利用交互集合對(duì)社交網(wǎng)絡(luò)表征算法進(jìn)行優(yōu)化,具體過程如下:

1)減小同一集合中的元素距離,提高元素間的相似度。在使用word2vec對(duì)向量初始化后,根據(jù)歐式距離求集合內(nèi)各節(jié)點(diǎn)ui的向量中心centre,取集合中心與原節(jié)點(diǎn)來(lái)計(jì)算節(jié)點(diǎn)新的初始化結(jié)果:

(7)

其中,f(ui)為用戶ui的向量表示,centre表示用戶ui所在交互集合的中心。

2)增加不同集合間的距離,提高類別間的辨識(shí)度。隨機(jī)對(duì)同一集合所有節(jié)點(diǎn)表征中的m維向量進(jìn)行優(yōu)化,使其在空間上屬于另一個(gè)區(qū)間。隨機(jī)產(chǎn)生小于節(jié)點(diǎn)向量維度的m個(gè)隨機(jī)數(shù)ran={r1,r2,…,rm}。根據(jù)集合ran對(duì)向量進(jìn)行優(yōu)化:

[v1,v2,…,vi,…,vd]×[spij]d×d

(8)

(9)

利用用戶的交互信息,優(yōu)化word2vec的初始化,使不同集合內(nèi)的用戶與其他集合在特征表示上有明顯差異,在不斷的學(xué)習(xí)中,使與其相似的節(jié)點(diǎn)也表現(xiàn)出同樣的特性。如果在選擇的n個(gè)優(yōu)化集合中出現(xiàn)同一類節(jié)點(diǎn),在相同的優(yōu)化策略下,其效果等同于選擇n×m維對(duì)某些節(jié)點(diǎn)進(jìn)行優(yōu)化。當(dāng)m較小時(shí)并不影響整體學(xué)習(xí)效果。

改進(jìn)后的社交網(wǎng)絡(luò)表征算法具體步驟為:

步驟1根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)分布,計(jì)算各節(jié)點(diǎn)游走次數(shù),生成相應(yīng)集合,按照節(jié)點(diǎn)劃分約束隨機(jī)游走過程,生成語(yǔ)料庫(kù)。

步驟2初始化節(jié)點(diǎn)向量并根據(jù)交互關(guān)系對(duì)向量進(jìn)行修改。

步驟3訓(xùn)練得到各節(jié)點(diǎn)的向量表示。

對(duì)整個(gè)算法而言,隨機(jī)游走和根據(jù)游走序列訓(xùn)練節(jié)點(diǎn)向量表示是消耗時(shí)間最多的步驟,引入節(jié)點(diǎn)劃分策略,使不同節(jié)點(diǎn)的游走次數(shù)得到不同的控制,能讓總游走次數(shù)降低、語(yǔ)料庫(kù)減小,訓(xùn)練時(shí)間隨之減少,同時(shí)利用交互集合可以提高最終表征的準(zhǔn)確度。

2.4 算法描述

本文基于遍歷約束和交互信息的社交網(wǎng)絡(luò)表征算法描述如下:

算法1社交網(wǎng)絡(luò)表征算法

輸入網(wǎng)絡(luò)拓?fù)銰=(V,E,W),向量維度d,最大游走次數(shù)r,游走長(zhǎng)度l,窗口大小k,交互關(guān)系follows,改變的維度m,改變的大小g

輸出d維的節(jié)點(diǎn)向量表征

1.function learnFeatures(G,d,r,l,k,follows,m,g)

2.walks=restrictedWalk(G,l,r)//根據(jù)網(wǎng)絡(luò)拓?fù)浼肮?jié)點(diǎn)//度數(shù)遍歷網(wǎng)絡(luò)，構(gòu)建網(wǎng)絡(luò)遍歷集合walks

3.initvec= initvec(k,d,walks,follows,m,g)//根據(jù)遍//歷結(jié)果及交互信息對(duì)節(jié)點(diǎn)表征進(jìn)行初始化

4.vec=train(walks,initvec)//利用自然語(yǔ)言模型對(duì)遍//歷結(jié)果進(jìn)行訓(xùn)練，得到最終表征結(jié)果

5.return vec

6.function restrictedWalk(G,l,r)//構(gòu)建網(wǎng)絡(luò)遍歷集合

7.removeSet = buildDifSetAccordNode(G)//根據(jù)網(wǎng)//絡(luò)節(jié)點(diǎn)度數(shù)設(shè)定不同的遍歷次數(shù)

8.for iter = 1 to r do

9.for nodes u∈V do

10.walks=buildWalkAccording(G)//遍歷節(jié)點(diǎn)構(gòu)建//walks

11.end for

12.V remove nodes which in removeSet[iter]//移除遍歷//次數(shù)達(dá)到閾值的節(jié)點(diǎn)

13.end for

14.return walks

15.function initvec(k,d,walks,follows,m,g)//對(duì)節(jié)點(diǎn)表//征進(jìn)行初始化

16.initialize_vec(walks)

17.for perFollows in follows

18.for node in perFollows

19.initvec(node)=(centre+vec(node))/2+[vi]1×d×[spanij]d×d//根據(jù)交互集合對(duì)極有可能屬于同一集合的//節(jié)點(diǎn)表征進(jìn)行向量?jī)?yōu)化

20.end for

21.end for

22.return initvec

以上偽代碼對(duì)算法流程進(jìn)行了簡(jiǎn)要表述:

1)函數(shù)restrictedWalk()根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)分布建立次數(shù)不等的遍歷集合,在之后的遍歷過程中不斷刪除遍歷次數(shù)達(dá)到指定閾值的節(jié)點(diǎn)集合。

2)函數(shù)stochasticGradientDescent()首先利用word2vec對(duì)各節(jié)點(diǎn)進(jìn)行初始化,然后根據(jù)交互集合對(duì)初始化后的節(jié)點(diǎn)實(shí)現(xiàn)優(yōu)化,最后通過大量訓(xùn)練集來(lái)表征學(xué)習(xí)整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

為驗(yàn)證本文算法的效率和準(zhǔn)確率,采用BlogCatalog和新浪微博數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。對(duì)相同的實(shí)驗(yàn)任務(wù),將本文算法與以下4種主流網(wǎng)絡(luò)表征算法進(jìn)行比較:

1)DeepWalk算法:根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),采用相同次數(shù)的隨機(jī)游走方式遍歷網(wǎng)絡(luò),生成語(yǔ)料庫(kù),直接使用word2vec模型進(jìn)行向量表征。

2)node2vec算法:與DeepWalk相比,該算法通過參數(shù)調(diào)節(jié)達(dá)到帶有偏置的隨機(jī)游走,游走可能趨于深度優(yōu)先或廣度優(yōu)先,同樣直接使用word2vec模型進(jìn)行向量表征。

3)Line算法:將深度優(yōu)先和廣度優(yōu)先策略結(jié)合,利用word2vec進(jìn)行表征。

4)ComEmbed算法:對(duì)社區(qū)和節(jié)點(diǎn)共同利用word2vec進(jìn)行優(yōu)化。

3.2 數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)所用數(shù)據(jù)集信息如下:

1)BlogCatalog:社交網(wǎng)絡(luò)數(shù)據(jù)集,數(shù)據(jù)從BlogCatalog網(wǎng)站爬取,多數(shù)主流表征算法采用該數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)。該數(shù)據(jù)集包含10 312個(gè)節(jié)點(diǎn)、333 983條邊和交互信息,節(jié)點(diǎn)表示不同的微博用戶,邊代表2個(gè)微博用戶之間存在著好友關(guān)系。數(shù)據(jù)集將10 312個(gè)用戶分成39類。

2)新浪微博:該數(shù)據(jù)集為爬取的新浪微博部分?jǐn)?shù)據(jù),包含1 701個(gè)節(jié)點(diǎn)(微博用戶)、29 439條邊(好友關(guān)系)、90 962條交互行為,數(shù)據(jù)集將用戶分為8類。

本次實(shí)驗(yàn)在個(gè)人計(jì)算機(jī)上進(jìn)行,實(shí)驗(yàn)環(huán)境如下:處理器為Intel(R) Core(TM) i5-2450M CPU 2.5 GHz雙核;內(nèi)存為8 GB;操作系統(tǒng)為Windows10 (64位)。

實(shí)驗(yàn)1分別利用DeepWalk算法、node2vec算法、Line算法、ComEmbed算法和本文算法在2個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果采用準(zhǔn)確率作為衡量指標(biāo),同時(shí)驗(yàn)證算法的時(shí)間效率。

為避免由參數(shù)設(shè)置帶來(lái)的誤差,本實(shí)驗(yàn)中節(jié)點(diǎn)最大遍歷次數(shù)與其他算法遍歷次數(shù)相同,結(jié)果使用相同的分類算法進(jìn)行對(duì)比驗(yàn)證。實(shí)驗(yàn)參數(shù)設(shè)置為:向量維度d=128,游走步長(zhǎng)walklength=80,窗口大小winsize=10,游走次數(shù)walknum=40。實(shí)驗(yàn)結(jié)果如表1、表2所示。

表1 實(shí)驗(yàn)1中各算法準(zhǔn)確率結(jié)果

表2 實(shí)驗(yàn)1中各算法運(yùn)行時(shí)間結(jié)果 min

5種算法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行維數(shù)為128的向量表征,采用50%帶標(biāo)簽的節(jié)點(diǎn)作為訓(xùn)練集,剩余部分作為測(cè)試集。從表1可以看出,本文算法在準(zhǔn)確率上優(yōu)于流行的網(wǎng)絡(luò)表征算法,在BlogCatalog數(shù)據(jù)集上達(dá)到0.421,比node2vec和ComEmbed分別提高39%和35%。在新浪微博數(shù)據(jù)集中,本文算法相對(duì)其他算法,在準(zhǔn)確率上也有明顯提高。從表2可以看出,對(duì)比其他算法,本文算法運(yùn)行時(shí)間下降均高于20%。

實(shí)驗(yàn)2在BlogCatalog數(shù)據(jù)集上,分別使用準(zhǔn)確率較高的node2vec算法和本文算法,研究游走次數(shù)walknum對(duì)算法性能的影響。實(shí)驗(yàn)參數(shù)設(shè)置為:向量維度d=128,游走步長(zhǎng)walklength=80,窗口大小winsize=10,游走次數(shù)walknum不斷增加。采用準(zhǔn)確率和F1值作為衡量指標(biāo),實(shí)驗(yàn)結(jié)果如表3、表4所示。

表3 實(shí)驗(yàn)2中2種算法準(zhǔn)確率結(jié)果

表4 實(shí)驗(yàn)2中2種算法F1值結(jié)果

從表3、表4可以看出,算法的準(zhǔn)確率和F1值均隨著游走次數(shù)walknum的增加而提高,當(dāng)walknum達(dá)到40后算法結(jié)果趨于平穩(wěn)。在準(zhǔn)確率上,本文算法在walknum=30時(shí),其結(jié)果已經(jīng)比walknum=40時(shí)node2vec的結(jié)果高出20%,當(dāng)walknum=40時(shí),本文算法F1值比node2vec算法提高了35%。

3.3 參數(shù)分析

本文算法包含若干參數(shù),其中多數(shù)為目前網(wǎng)絡(luò)表征中都會(huì)使用的參數(shù)(如游走步長(zhǎng)walklength、向量維度d、游走次數(shù)walknum、窗口大小winsize),除此之外,本文算法還引入?yún)?shù)m、g,m為隨機(jī)優(yōu)化向量維數(shù),g為向量分量的大小范圍。

在已有的網(wǎng)絡(luò)表征算法中,已經(jīng)說明游走步長(zhǎng)walklength對(duì)模型的影響。本次實(shí)驗(yàn)主要研究窗口大小winsize、m、g對(duì)算法性能的影響,實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 各參數(shù)對(duì)算法性能的影響

從圖2可以看出:

1)winsize的設(shè)置和傳統(tǒng)自然語(yǔ)言的表征算法有較大區(qū)別,當(dāng)winsize∈[4,8]時(shí),算法效果較好,當(dāng)winsize超過10以后,算法效果會(huì)趨于穩(wěn)定。造成該結(jié)果的原因可能是,自然語(yǔ)言處理在一定程度上符合大數(shù)定理,而社交網(wǎng)絡(luò)的處理離不開“六度分離”理論。

2)m的選擇受向量維度d的影響,已有算法證明當(dāng)d達(dá)到100之后算法表征效果趨于穩(wěn)定。本文選取128作為向量表征維度,研究m對(duì)算法性能的影響?？梢钥闯?維數(shù)的多少對(duì)算法有明顯的影響,當(dāng)維數(shù)較大時(shí),算法的準(zhǔn)確性會(huì)降低,原因是選擇維數(shù)太大不僅不會(huì)增加類之間的區(qū)分度,還會(huì)使所有維度的修改趨于平均化。

3)分析向量改變大小g對(duì)算法性能的影響,通過實(shí)驗(yàn)結(jié)果可以看出,當(dāng)g=3時(shí)算法效果最好,當(dāng)g超過5以后算法效果會(huì)趨于穩(wěn)定。

4 結(jié)束語(yǔ)

本文分析社交網(wǎng)絡(luò)中節(jié)點(diǎn)自身好友關(guān)系的數(shù)量,提出一種改進(jìn)的社交網(wǎng)絡(luò)表征算法。根據(jù)好友分布不均衡的特性控制網(wǎng)絡(luò)遍歷次數(shù),指導(dǎo)隨機(jī)游走后生成較小的語(yǔ)料庫(kù),同時(shí)根據(jù)交互關(guān)系優(yōu)化節(jié)點(diǎn)向量。實(shí)驗(yàn)結(jié)果表明,該算法在準(zhǔn)確率和效率上具有優(yōu)勢(shì)。社交網(wǎng)絡(luò)包含豐富的信息,如何充分利用這些信息構(gòu)造更準(zhǔn)確的節(jié)點(diǎn)表征模型,將是下一步的研究方向。