基于LBSN中錨鏈接方法的鏈路預測模型

黃壽孟，夏王霞

(三亞學院 信息與智能工程學院，海南 三亞 572022)

0 引言

大數據環境下的社交網絡，數據具有多維性和關聯性，那么如何充分利用好這些特性呢？這就需要構建數學模型來挖掘出這些數據之間的潛在關系信息，比如基于地址位置的社交網絡(Location-based Social Network，簡稱LBSN)，一般包含兩種數據[1]67：一種是網絡中用戶本身的數據，另一種是用戶間存在的關系數據。從LBSN中挖掘出用戶間的時空信息進行各種應用活動[2]79，比如好友推薦[3]7、興趣推薦[4]、軌跡恢復[5]108、行為預測[6]120等應用場景。其實在社交網絡分析中，鏈路預測一直是信息推薦系統的研究熱點，它是從網絡中已知節點信息找出可能存在節點鏈接的信息。就目前社交網絡而言，在鏈路預測領域，可根據用戶簽到記錄和社交網絡兩種數據來實現信息推薦。Li Zhepeng等人[1]1938提出在LBSN中這兩種異構數據融合的預測方法，利用網絡表示學習和矩陣分解數據節點信息，通過拼接融合方案完成預測任務。Hu Wei等人[2]206運用概率學方法將網絡用戶時間行為與社會理論融合構建鏈路模型。Li Jichao等人[7]10利用網絡結構與節點形成時間的關聯信息構建預測方法，而Liang Wenxin等人[8]1111量化用戶節點社交圖屬性、用戶檔案信息和移動特征之間的關聯來建模預測好友關系，并綜合用戶話題特征和節點拓撲結構構建聯合預測模型。Ling Jiang等人[9]211研究了網絡交叉視圖，通過學習鏈路表示與用戶屬性表示來完成鏈路預測任務。從不同角度完成復雜網絡鏈路預測任務的還有異構數據源進行混合預測[10]305、基于聚類分析[11]144、從信息學分析角度[12]、基于節點局部相似性[13]、基于資源傳輸匹配度[14]、基于互信息[15]57等。為了進一步提升鏈路預測性能和準確度，本研究提出一種錨鏈接方案取代文獻[1]中的數據拼接融合方案[1]1938，更深入挖掘LBSN中節點鏈接信息及其關聯，錨鏈接節點就是兩種不同數據的公共節點，它們的映射關系由神經網絡算法完成。

1 相關工作

1.1 網絡表示學習

提取網絡節點的信息方法有很多，目前比較流行的是網絡表示學習方法[16]，它是運用深度學習技術對網絡空間量化降維過程，從而提取出網絡中各節點的特征向量。如圖1所示，Deep Walk[7]12實現網絡表示學習獲取用戶節點向量化的大致流程。

圖1 網絡表示學習流程

目前在LBSN的好友推薦領域，利用網絡表示學習可以完成低維空間向量表示、節點分類與聚類等任務，通過挖掘社交用戶網絡拓撲結構中的潛在關系規律及特征，對LBSN網絡關系進行建模，得到以向量表示出LBSN社交關系拓撲結構中的各用戶節點和各節點之間的用戶關聯信息。

1.2 矩陣分解

矩陣分解其實是一種矩陣的變換方法，為了完成矩陣的降維任務，將原矩陣拆分為多個相關聯的矩陣[17]。推薦系統中常常使用矩陣分解來過濾某些數據從而完成推薦任務[18]。比如用戶給電影打分，假設從觀影購票系統獲取所有數據，構建出用戶評分表，如圖2所示，行值為用戶ID，列值為電影ID，符號？表示缺失評分值，即某用戶對某電影未觀看不評分的現象。現在需要預測出這些缺失的評分值(假設分值范圍為1～5)，首先將評分表矩陣分解為用戶矩陣與電影矩陣的乘積關系，希望相乘結果與原評分矩陣的分值盡可能接近(損失函數的條件)，經過不斷的迭代多輪訓練優化后得到收斂模型(即損失函數)，從而將相乘得到的新矩陣代替原矩陣中缺失的值，即預測出該用戶對未觀看的電影興趣值。

圖2 矩陣分解觀影評分圖

1.3 相關的預測模型

Walk2friends[15]57模型僅提取用戶移動特征；DeepWalk[7]15模型通過游走方式提取用戶節點序列；LINE[9]211模型采用節點共現與條件概率建模；GraRep[2]81模型構造轉移矩陣提取節點相似性；Node2vec[11]144利用網絡局部與全局屬性提取節點的領域；Struc2vec[8]1111模型捕獲節點結構向量化建模。本研究采用節點信息(用戶簽到記錄)和節點結構關系(矩陣表示)來進行潛在關系建模，并使用錨鏈接算法將兩者數據融合進行點對關系的向量化，通過訓練集與測試集來優化預測性能。

2 預測方法

2.1 基本定義

任意兩個社交網絡Gv=(Uv,Ev)和Gn=(Un,En)，傳統錨鏈接方法直接預測兩個用戶ui∪Uv和uj∪Un是否同一個人(即ui=uj)，而本文構建AL-P模型是通過兩個LBSN中的共同用戶來調整兩者的向量空間，即錨鏈接滿足二進制鑒別函數φ：Uv×Un→{0,1}，其對應的公式為

其中：()DEC表示用戶節點的向量編碼，即節點相似度的量化值；()ENC表示最大維度保存網絡屬性，即節點向量化維度值；P()是由用戶定義的節點間相似性度量值。

2.2 預測模型

圖3 AL-P預測模型

2.3 錨鏈接算法

輸入：兩個異構網絡Gv和Gn；預訓練函數φ和F；參數W和b，有標簽的錨鏈接集合Ev。

1:repeat

2: for each epoch do

3:for i = 1 to N do

6:根據更新參數W和b

7:end for

8:計算y=Ftrue和a=o′(Fpredicted)

9:再次更新參數W和b

10:end for

11:until 收斂

3 實驗分析

3.1 實驗準備工作

本實驗采用基于LBSN的Gowalla和Foursquare兩種不同的開源數據集[9]213(其中@NY表示紐約，@TY表示東京，@WHG表示華盛頓，@CCG表示芝加哥)，如表1所示，從中提取用戶關系拓撲圖和用戶簽到記錄，以及對相關數據進行預處理操作，其結果如下表2所示。

表1 實驗數據集情況

表2 數據預處理結果

本實驗對照基準模型有Walk2friends[5]108和DeepWalk[6]122，其中Walk2friends提取用戶移動特征，而DeepWalk提取用戶節點序列，兩種模型的操作方法統一用隨機選擇平均Average。評估指標有AUC、精度、查全率和F1值(精度與查全率的調和平均)。

3.2 實驗結果

評估指標AUC可以檢測鏈路預測模型的性能，它表示正/負樣本的概率值，其實驗結果如表3所示，說明在不同的數據集中，AL-P模型的AUC值都優于現有模型Walk2friends，DeepWalk，LINE，GraRep，Node2vec和Struc2vec，這里的數據融合操作統一采用Average操作。

表3 AL-P的AUC預測結果

對于Foursquare數據集(@NY與@TY)和Gowalla數據集(@WHG與@CCG)，完成評估指標精度、查全率、F1值的衡量實驗，其中表4是Foursquare數據集的預測結果，表5是Gowalla數據集的預測結果。從表4和表5中可以得到在鏈路預測任務中，AL-P預測效果在兩個數據集中是最佳的，這是因為AL-P模型加入用戶簽到偏好信息，讓社交網絡信息比用戶移動信息更具有指示性，有效提升鏈路預測的準確度，而walk2friends結果差是由于預測時缺少用戶網絡結構信息。

表4 Foursquare數據集的預測結果

表5 Gowalla數據集的預測結果

4 結語

為了提升鏈路預測的效果，本研究提出一種錨鏈方法，通過用戶向量對齊完成兩個異構空間的映射，得到新的用戶訪問偏好向量，訓練融合后更新出社交關系向量，從而進一步提升鏈路預測的綜合性能。不足之處是從移動數據和社交數據中如何學到更好的用戶表示，挖掘相關用戶數據的潛在價值，若在時空行為上建模，則能更好完成預測任務。

(責任編輯：潘姝靜)