基于遍歷約束與交互信息增強的社交網絡表征算法

石立鵬,王 莉

(太原理工大學 a.信息與計算機學院; b.大數據學院,山西 晉中 030600)

0 概述

網絡技術的迅猛發展,使社交網絡成為覆蓋用戶最廣、傳播影響力最大的互聯網發展產物之一,其蘊含著巨大的商業價值。

社交網絡的主體是網絡中的用戶,也即網絡中的節點。網絡規模的不斷壯大對社交網絡表征算法提出了新的挑戰。如何對社交網絡進行準確、高效地表征,成為一個重要的研究方向。一個性能良好的表征算法便于計算用戶間的相似度、實現用戶間的鏈預測和用戶社區劃分等。傳統社交網絡表征算法多數通過人為特征定義、特征提取、矩陣運算以進行用戶向量表示。但隨著網絡節點(社交網絡用戶)數量的增加,傳統方法在準確率和效率上表現出一定的不足。

近年來,無監督算法在很多研究領域取得了很好的效果。在自然語言處理方面,word2vec模型被提出。受該模型的啟發,在網絡學習中,出現了DeepWalk、Line、node2vec及ComEmbed[1]網絡表征算法。這些算法能夠避免傳統方法中人為提取特征和大量矩陣運算的問題,但都只利用網絡的拓撲結構,并未涉及網絡的交互信息。而用戶間的交互行為恰是社交網絡的重要組成部分,交互信息對網絡表征具有十分積極的作用。

針對上述算法存在的不足,在現有網絡表征算法和word2vec模型的基礎上,本文依據社交網絡特性,提出一種改進的基于遍歷約束與交互信息的網絡表征算法。該算法分析社交網絡單個節點的特征,通過增加遍歷規則來提高學習效率,利用網絡用戶間的交互信息改進自然語言模型word2vec,以提高結果準確率。

1 相關工作

1.1 自然語言處理模型

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

1.2 網絡表征算法

網絡表征問題一直受到許多研究者的關注,現有特征表示方法主要有:

1)傳統的譜方法:文獻[6-9]將網絡轉換成矩陣,分別利用鄰接矩陣和拉普拉斯矩陣,通過矩陣運算、特征分解、降維等方法得到網絡表征。但這種方法對較大型的網絡并不適用,隨著網絡中節點和關系數目的增加,矩陣計算將耗費大量時間及計算機資源,且最終得到的向量表示也并不理想。

2)利用自然語言模型的方法:受自然語言處理模型的影響,近年來,很多研究者將網絡與自然語言模型相結合,提出很多網絡表征算法。文獻[10]在DeepWalk中通過網絡隨機游走產生節點序列,類似自然語言中的句子,從而利用自然語言處理模型學習網絡節點的特征表示。文獻[11]將深度優先遍歷策略和廣度優先遍歷策略相結合,對語料庫進行優化。文獻[12]提出node2vec模型,采用帶有偏置的隨機游走策略進一步提高網絡表征的準確性。與傳統的網絡表征算法相比,這些算法利用機器學習的設計思想,在降低計算復雜度的同時能取得較好的網絡表征效果。

在自然語言中,句子是滿足特定語法規則的,單詞間的關系是線性的,每個單詞都存在特定的上下文。文獻[13]認為,網絡的結構是非線性的,通過不同的遍歷方式產生的序列直接影響網絡節點表征的結果。較普遍的遍歷策略有深度優先、廣度優先和隨機遍歷,不同遍歷策略對結果會產生不同的影響,但目前仍然缺少普適性的遍歷策略來提高網絡表征的準確性。

1.3 社交網絡表征

對于社交網絡,文獻[14-15]針對用戶行為以及網絡拓撲結構特征,對網絡用戶進行矢量化表示。文獻[16]通過用戶興趣和拓撲結構實現社交網絡的好友推薦。文獻[17]基于社交網絡拓撲結構,利用網絡的連通性進行網絡用戶表征,最終實現好友推薦。文獻[18]結合網絡拓撲結構和用戶信息對網絡用戶進行表征。這些方法都基于大量的矩陣運算,并不適合表征大型社交網絡。

在利用自然語言模型對社交網絡進行表征時,文獻[19]將節點信息加入網絡表征,可以減少矩陣運算,但其表征效果并沒有得到明顯提高。

現有表征算法只考慮網絡本身,并未有效利用社交網絡交互信息。而對于社交網絡,其本質是一個用戶交互平臺,因此,網絡交互信息對表征起著重要作用。本文根據社交網絡鄰居數量來約束網絡遍歷,同時利用網絡交互信息對網絡表征的學習過程進行優化。

2 改進的社交網絡表征算法

2.1 網絡表征學習模型

機器學習定義目標函數f,利用合適的優化策略對函數進行優化,以得到較好的結果。對于網絡表征算法,一般采用對數似然函數。設f(w)為節點w的向量表示,Ns(w)為遍歷策略s下w的鄰居。式(1)為網絡表征的優化目標:通過遍歷過程中的鄰居節點以最大化網絡節點w的對數概率。

(1)

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

(2)

(3)

則從根到葉子節點w的路徑選擇概率對應多次二分類的概率乘積:

(4)

其中,hjw表示節點w的Huffman編碼中的第j位,lw表示w的Huffman編碼長度,θjw為該路徑中非葉子節點的向量表示。最終的優化函數為:

(5)

根據遍歷序列,采用隨機梯度上升方法對參數θ及節點w的鄰居進行優化,并更新各向量。

2.2 基于網絡結構的遍歷優化

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

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

圖1 節點遍歷約束示意圖

按照長尾分布,將所有節點平均度數作為“頭”和“尾”的分割。對于“頭”中的節點,其好友關系復雜,根據算法給出的最大游走次數遍歷生成語料庫,對于“尾”中的節點,根據節點與均值的比值約束游走次數。各節點游走次數計算如下:

(6)

其中,vi代表網絡中的第i個節點,deg(vi)表示節點vi的度數,walknum為最大游走次數,avg為所有節點的平均度數,count(vi)計算節點vi的遍歷次數,并作為遍歷約束條件。

本文算法只限制以該節點為起點的隨機游走次數,該節點仍然會在其他節點的隨機游走序列中出現。根據word2vec原理,對于度數較低的點,其向量表示同樣可以根據包含該節點的其他游走序列進行優化。

2.3 基于交互行為的算法改進

網絡表征算法及word2vec模型的目的是使相似節點或單詞具有更加接近的特征表示。在word2vec模型中,單詞初始化向量是隨機的,向量表示的距離也是隨機的,但通過大量的語料訓練可使具有相似含義的單詞更加接近。這是因為自然語言中的句子是線性的,可以通過大量的訓練得到較準確的表達。現有網絡表征算法大都聚焦于調整網絡遍歷策略,然后直接利用word2vec模型得到節點表征。由于網絡的非線性特性,當網絡表征準確率趨于穩定后,通過擴充訓練集來提高算法表征效果將變得十分困難。

社交網絡作為用戶交互平臺,存在大量的用戶交互信息,這些信息對社交網絡表征具有積極的意義。通過對社交網絡的分析發現,用戶在一段時間內存在交互行為的好友,極有可能屬于同一個或有限幾個社交圈。因此,可以根據社交網絡的這一特點對word2vec模型進行改進,雖然這無法完全避免由網絡非線性結構帶來的困擾,但卻可以使模型更適合社交平臺。

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

2.3.1 交互集合選擇

社交網絡用戶的交互行為很頻繁,多數用戶都會存在數量不等的交互信息。為避免平均化,應選擇交互量較大用戶的交互好友作為單個優化集合,選擇交集較小的不同用戶的交互集合作為優化對象。

交互集合作為算法優化的依據,需滿足如下條件:1)應選擇交互關系數較大的多個用戶的交互集合,以減少集合個數,同時避免優化結果的平均化;2)單個交互集合內元素與同一用戶存在交互行為;3)不同交互集合的交集盡可能小,避免對同一用戶進行多次優化從而降低區分度。

2.3.2 表征算法優化

利用交互集合對社交網絡表征算法進行優化,具體過程如下:

1)減小同一集合中的元素距離,提高元素間的相似度。在使用word2vec對向量初始化后,根據歐式距離求集合內各節點ui的向量中心centre,取集合中心與原節點來計算節點新的初始化結果:

(7)

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

2)增加不同集合間的距離,提高類別間的辨識度。隨機對同一集合所有節點表征中的m維向量進行優化,使其在空間上屬于另一個區間。隨機產生小于節點向量維度的m個隨機數ran={r1,r2,…,rm}。根據集合ran對向量進行優化:

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

(8)

(9)

利用用戶的交互信息,優化word2vec的初始化,使不同集合內的用戶與其他集合在特征表示上有明顯差異,在不斷的學習中,使與其相似的節點也表現出同樣的特性。如果在選擇的n個優化集合中出現同一類節點,在相同的優化策略下,其效果等同于選擇n×m維對某些節點進行優化。當m較小時并不影響整體學習效果。

改進后的社交網絡表征算法具體步驟為:

步驟1根據網絡節點分布,計算各節點游走次數,生成相應集合,按照節點劃分約束隨機游走過程,生成語料庫。

步驟2初始化節點向量并根據交互關系對向量進行修改。

步驟3訓練得到各節點的向量表示。

對整個算法而言,隨機游走和根據游走序列訓練節點向量表示是消耗時間最多的步驟,引入節點劃分策略,使不同節點的游走次數得到不同的控制,能讓總游走次數降低、語料庫減小,訓練時間隨之減少,同時利用交互集合可以提高最終表征的準確度。

2.4 算法描述

本文基于遍歷約束和交互信息的社交網絡表征算法描述如下:

算法1社交網絡表征算法

輸入網絡拓撲G=(V,E,W),向量維度d,最大游走次數r,游走長度l,窗口大小k,交互關系follows,改變的維度m,改變的大小g

輸出d維的節點向量表征

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

2.walks=restrictedWalk(G,l,r)//根據網絡拓撲及節點//度數遍歷網絡，構建網絡遍歷集合walks

3.initvec= initvec(k,d,walks,follows,m,g)//根據遍//歷結果及交互信息對節點表征進行初始化

4.vec=train(walks,initvec)//利用自然語言模型對遍//歷結果進行訓練，得到最終表征結果

5.return vec

6.function restrictedWalk(G,l,r)//構建網絡遍歷集合

7.removeSet = buildDifSetAccordNode(G)//根據網//絡節點度數設定不同的遍歷次數

8.for iter = 1 to r do

9.for nodes u∈V do

10.walks=buildWalkAccording(G)//遍歷節點構建//walks

11.end for

12.V remove nodes which in removeSet[iter]//移除遍歷//次數達到閾值的節點

13.end for

14.return walks

15.function initvec(k,d,walks,follows,m,g)//對節點表//征進行初始化

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//根據交互集合對極有可能屬于同一集合的//節點表征進行向量優化

20.end for

21.end for

22.return initvec

以上偽代碼對算法流程進行了簡要表述:

1)函數restrictedWalk()根據網絡節點分布建立次數不等的遍歷集合,在之后的遍歷過程中不斷刪除遍歷次數達到指定閾值的節點集合。

2)函數stochasticGradientDescent()首先利用word2vec對各節點進行初始化,然后根據交互集合對初始化后的節點實現優化,最后通過大量訓練集來表征學習整個網絡節點。

3 實驗結果與分析

3.1 實驗設計

為驗證本文算法的效率和準確率,采用BlogCatalog和新浪微博數據集進行實驗。對相同的實驗任務,將本文算法與以下4種主流網絡表征算法進行比較:

1)DeepWalk算法:根據網絡拓撲結構,采用相同次數的隨機游走方式遍歷網絡,生成語料庫,直接使用word2vec模型進行向量表征。

2)node2vec算法:與DeepWalk相比,該算法通過參數調節達到帶有偏置的隨機游走,游走可能趨于深度優先或廣度優先,同樣直接使用word2vec模型進行向量表征。

3)Line算法:將深度優先和廣度優先策略結合,利用word2vec進行表征。

4)ComEmbed算法:對社區和節點共同利用word2vec進行優化。

3.2 數據集及實驗環境

實驗所用數據集信息如下:

1)BlogCatalog:社交網絡數據集,數據從BlogCatalog網站爬取,多數主流表征算法采用該數據集進行對比實驗。該數據集包含10 312個節點、333 983條邊和交互信息,節點表示不同的微博用戶,邊代表2個微博用戶之間存在著好友關系。數據集將10 312個用戶分成39類。

2)新浪微博:該數據集為爬取的新浪微博部分數據,包含1 701個節點(微博用戶)、29 439條邊(好友關系)、90 962條交互行為,數據集將用戶分為8類。

本次實驗在個人計算機上進行,實驗環境如下:處理器為Intel(R) Core(TM) i5-2450M CPU 2.5 GHz雙核;內存為8 GB;操作系統為Windows10 (64位)。

實驗1分別利用DeepWalk算法、node2vec算法、Line算法、ComEmbed算法和本文算法在2個數據集上進行實驗。實驗結果采用準確率作為衡量指標,同時驗證算法的時間效率。

為避免由參數設置帶來的誤差,本實驗中節點最大遍歷次數與其他算法遍歷次數相同,結果使用相同的分類算法進行對比驗證。實驗參數設置為:向量維度d=128,游走步長walklength=80,窗口大小winsize=10,游走次數walknum=40。實驗結果如表1、表2所示。

表1 實驗1中各算法準確率結果

表2 實驗1中各算法運行時間結果 min

5種算法對網絡節點進行維數為128的向量表征,采用50%帶標簽的節點作為訓練集,剩余部分作為測試集。從表1可以看出,本文算法在準確率上優于流行的網絡表征算法,在BlogCatalog數據集上達到0.421,比node2vec和ComEmbed分別提高39%和35%。在新浪微博數據集中,本文算法相對其他算法,在準確率上也有明顯提高。從表2可以看出,對比其他算法,本文算法運行時間下降均高于20%。

實驗2在BlogCatalog數據集上,分別使用準確率較高的node2vec算法和本文算法,研究游走次數walknum對算法性能的影響。實驗參數設置為:向量維度d=128,游走步長walklength=80,窗口大小winsize=10,游走次數walknum不斷增加。采用準確率和F1值作為衡量指標,實驗結果如表3、表4所示。

表3 實驗2中2種算法準確率結果

表4 實驗2中2種算法F1值結果

從表3、表4可以看出,算法的準確率和F1值均隨著游走次數walknum的增加而提高,當walknum達到40后算法結果趨于平穩。在準確率上,本文算法在walknum=30時,其結果已經比walknum=40時node2vec的結果高出20%,當walknum=40時,本文算法F1值比node2vec算法提高了35%。

3.3 參數分析

本文算法包含若干參數,其中多數為目前網絡表征中都會使用的參數(如游走步長walklength、向量維度d、游走次數walknum、窗口大小winsize),除此之外,本文算法還引入參數m、g,m為隨機優化向量維數,g為向量分量的大小范圍。

在已有的網絡表征算法中,已經說明游走步長walklength對模型的影響。本次實驗主要研究窗口大小winsize、m、g對算法性能的影響,實驗結果如圖2所示。

圖2 各參數對算法性能的影響

從圖2可以看出:

1)winsize的設置和傳統自然語言的表征算法有較大區別,當winsize∈[4,8]時,算法效果較好,當winsize超過10以后,算法效果會趨于穩定。造成該結果的原因可能是,自然語言處理在一定程度上符合大數定理,而社交網絡的處理離不開“六度分離”理論。

2)m的選擇受向量維度d的影響,已有算法證明當d達到100之后算法表征效果趨于穩定。本文選取128作為向量表征維度,研究m對算法性能的影響。可以看出,維數的多少對算法有明顯的影響,當維數較大時,算法的準確性會降低,原因是選擇維數太大不僅不會增加類之間的區分度,還會使所有維度的修改趨于平均化。

3)分析向量改變大小g對算法性能的影響,通過實驗結果可以看出,當g=3時算法效果最好,當g超過5以后算法效果會趨于穩定。

4 結束語

本文分析社交網絡中節點自身好友關系的數量,提出一種改進的社交網絡表征算法。根據好友分布不均衡的特性控制網絡遍歷次數,指導隨機游走后生成較小的語料庫,同時根據交互關系優化節點向量。實驗結果表明,該算法在準確率和效率上具有優勢。社交網絡包含豐富的信息,如何充分利用這些信息構造更準確的節點表征模型,將是下一步的研究方向。