基于位置的社交網(wǎng)絡中基于時空關(guān)系的超網(wǎng)絡鏈接預測方法

胡 敏，陳元會，黃宏程

(重慶郵電大學通信與信息工程學院，重慶400065)(*通信作者電子郵箱huanghc@cqupt.edu.cn)

0 引言

隨著計算機信息技術(shù)的不斷發(fā)展和互聯(lián)網(wǎng)的迅速普及，在線社交平臺已經(jīng)成為人們生活中不可或缺的一部分，人們可以通過這個平臺建立自己的好友關(guān)系網(wǎng)，與好友進行即時的交流互動，這很大程度上方便了人們的生活;特別是近年來，基于位置的社交網(wǎng)絡(Location-Based Social Network，LBSN)的出現(xiàn)，使得一些位置服務在短時間內(nèi)受到了大量用戶的推崇，獲得了極大的成功。在LBSN中，用戶可以在他去過的位置進行簽到，并向好友分享自己的簽到地點，這種簽到行為能夠真實反映用戶的位置活動，使得線上虛擬世界和線下物理世界之間建立起密切聯(lián)系［1］，為社會網(wǎng)絡鏈接預測帶來了新的機遇和挑戰(zhàn)。

鏈接預測是社會網(wǎng)絡分析與挖掘中的一個重要方法［2］，其主要目的是挖掘網(wǎng)絡中可能存在的缺失鏈接或者未來鏈接。目前研究者們已經(jīng)提出了許多基于同構(gòu)網(wǎng)絡的鏈接預測方法，劉思等［3］針對隨機游走方法存在較強的隨機性問題，利用Deep Walk學習網(wǎng)絡中各節(jié)點間的潛在網(wǎng)絡結(jié)構(gòu)相似性，并指導隨機游走過程。Duan等［4］通過引入一種集成方法解決了大規(guī)模網(wǎng)絡下鏈接預測問題。這些方法在一定程度上解決了同構(gòu)網(wǎng)絡中的鏈接預測問題，但這些方法并不適用于異構(gòu)網(wǎng)絡?；谖恢玫纳缃痪W(wǎng)絡是一類異構(gòu)網(wǎng)絡，異構(gòu)網(wǎng)絡是指網(wǎng)絡中存在不止一種類型的節(jié)點和邊(例如:位置節(jié)點和用戶節(jié)點、用戶 用戶邊、用戶 位置邊等);因此，越來越多的研究者開始研究LBSN中的鏈接預測方法。Scellato等［5］發(fā)現(xiàn)在Gowalla中30%的新鏈接發(fā)生在有過相同簽到位置的用戶間，進而通過位置特征、社交特征以及全局特征，提高了鏈接預測的準確性。該方法雖然通過位置關(guān)系緩解了數(shù)據(jù)稀疏性問題，但只考慮了兩跳之內(nèi)的預測空間，使得預測精度存在一定的瓶頸。Valverde-Rebaza等［6］探索了用戶的移動模式和社會模式，提出了內(nèi)外共同位置(Within and Outside of Common Places，WOCP)、共同鄰居位置(Common Neighbors of Places，CNP)、總共和局部重疊位置(Total and Partial Overlapping of Places，TPOP)三種新特征，并通過實驗驗證了特征的有效性。Bayrak等［7］考慮到不同類別的位置對于鏈接建立的影響程度不同，提出了兩種新的基于類別的特征，實驗表明，新引入的特征提高了鏈接預測性能。

以上方法主要是在社會因素的基礎上引入了位置因素的影響，通過這種額外的“資源”達到了提高預測性能的目的。時間因素對于鏈接預測也有著一定的影響。Cheng等［8］通過簽到時間間隔、位置熵以及共同位置信息預測用戶之間的朋友關(guān)系。Crandall等［9］發(fā)現(xiàn)如果兩個用戶在相同的時間和相同的地點出現(xiàn)過，即使時空共現(xiàn)的次數(shù)比較少，也會極大增加他們之間產(chǎn)生鏈接的概率;Li等［10］也得到了相同的結(jié)論。然而時間因素的引入，使得本就稀疏的網(wǎng)絡變得更加稀疏，因此單獨考慮這一種因素顯得不夠合理。

針對數(shù)據(jù)的稀疏性問題，劉怡君等［11］首次提出了基于超網(wǎng)絡中的鏈路預測方法，通過引入超三角結(jié)構(gòu)作為相似性指標，能夠度量不同層網(wǎng)絡對鏈接產(chǎn)生的影響，提高預測性能。方哲等［12］在此基礎上提出了一種加權(quán)超網(wǎng)絡中的鏈接預測方法，通過加權(quán)超邊構(gòu)建加權(quán)超三角形結(jié)構(gòu)，并對節(jié)點間的鏈接關(guān)系進行預測，實驗證明，權(quán)值的引入提高了異構(gòu)網(wǎng)絡中的鏈接預測性能。文獻［13－14］也驗證了權(quán)值的引入對異構(gòu)網(wǎng)絡預測性能有較大影響。但是在基于位置的社交網(wǎng)絡中，邊權(quán)值不僅存在于同構(gòu)邊之間，同時存在于異構(gòu)邊之間，現(xiàn)有大多數(shù)研究僅考慮可觀測邊權(quán)值對網(wǎng)絡的影響［14－15］(如用戶對項目的評分、評論次數(shù)等)，忽略了網(wǎng)絡中不可觀測的邊權(quán)值，難以挖掘整個網(wǎng)絡的特性，同時目前基于超網(wǎng)絡的方法僅僅考慮了簡單的超三角結(jié)構(gòu)，缺乏對更深層次超邊結(jié)構(gòu)的發(fā)現(xiàn)，無法挖掘更多的隱含關(guān)系。

針對以上問題，本文提出了一種LBSN中基于時空關(guān)系的超網(wǎng)絡鏈接預測方法。該方法可以有效融合時間因素、社交因素、位置因素的影響，并且能夠合理量化網(wǎng)絡邊權(quán)重，較好地緩解數(shù)據(jù)稀疏性問題，同時能夠提高網(wǎng)絡的解釋性以及預測性能。

本文的主要工作如下:

1)針對LBSN中網(wǎng)絡的異構(gòu)性以及時空關(guān)系特性，提取時空節(jié)點，將網(wǎng)絡劃分成“時空 用戶 位置 類別”四層超網(wǎng)絡，通過該模型可以將時間因素通過節(jié)點的形式有效融入到超網(wǎng)絡中，以一種新穎的方式解決了因時間維度缺失所帶來的預測精度缺失問題。

2)為了使網(wǎng)絡更加符合實際，本文基于用戶影響力、隱關(guān)聯(lián)關(guān)系、用戶偏好以及節(jié)點度信息，量化超網(wǎng)絡中的相關(guān)邊權(quán)值，構(gòu)建四層加權(quán)超網(wǎng)絡模型，邊權(quán)值的定義和量化使得網(wǎng)絡中節(jié)點間的關(guān)聯(lián)關(guān)系更加準確，有助于提高模型的可解釋性以及預測精度。

3)在加權(quán)超網(wǎng)絡模型的基礎上，定義多種類型的超邊結(jié)構(gòu)，提出一種LBSN中的超網(wǎng)絡鏈接預測方法，通過該方法捕捉用戶之間潛在的多種關(guān)聯(lián)關(guān)系，有效解決了數(shù)據(jù)稀疏性問題，同時提高了預測準確度。

1 問題定義

1.1 相關(guān)定義

定義1 時空子網(wǎng)GT=(VT，ET，WT)。

時空子網(wǎng)GT是基于時空節(jié)點和時空節(jié)點間的關(guān)聯(lián)構(gòu)成的網(wǎng)絡。其中:VT表示時空節(jié)點，如果有兩個或兩個以上的用戶在某個特定的時間段共同訪問了某個位置，那么該位置就被稱為一個時空節(jié)點;ET表示時空節(jié)點之間的有向連邊，即兩個時空節(jié)點之間的關(guān)聯(lián)關(guān)系;WT表示時空節(jié)點之間的關(guān)聯(lián)權(quán)重。

定義2 用戶子網(wǎng)GU=(VU，EU，WU)。

用戶子網(wǎng)GU是基于用戶節(jié)點和用戶節(jié)點間的關(guān)系構(gòu)成的網(wǎng)絡。其中:VU表示用戶節(jié)點;EU表示用戶節(jié)點之間的有向連邊，即兩個用戶節(jié)點之間的社會關(guān)系;WU表示用戶節(jié)點之間的關(guān)聯(lián)權(quán)重。

定義3 位置子網(wǎng)GP=(VP，EP，WP)。

位置子網(wǎng)GP是基于位置節(jié)點和位置節(jié)點間的關(guān)聯(lián)構(gòu)成的網(wǎng)絡。其中:VP表示位置節(jié)點;EP表示位置節(jié)點之間的有向連邊，即兩個位置節(jié)點之間的關(guān)聯(lián)關(guān)系;WP表示位置節(jié)點之間的關(guān)聯(lián)權(quán)重。

定義4 類型子網(wǎng)GC=(VC，EC，WC)。

類型子網(wǎng)GC是基于類型節(jié)點和類型節(jié)點間的關(guān)聯(lián)構(gòu)成的網(wǎng)絡。其中:VC表示類型節(jié)點;EC表示類型節(jié)點之間的有向連邊，即兩個類型節(jié)點之間的關(guān)聯(lián)關(guān)系;WC表示類型節(jié)點之間的關(guān)聯(lián)權(quán)重。

1.2 問題形式化

為了形式化地描述本文研究的科學問題，首先假設G=(V，E，W)是本文研究的基于位置的社交網(wǎng)絡，以及網(wǎng)絡中的用戶行為數(shù)據(jù)B={(b，vi)|vi∈V}。在上述定義的基礎上，量化子網(wǎng)間的關(guān)聯(lián)權(quán)重WM，則網(wǎng)絡可以劃分成“時空 用戶

1.2.1 問題輸入

基于上述定義，本文研究內(nèi)容的輸入為:

1)基于位置的社交網(wǎng)絡G=(V，E，W);

2)絡中的用戶行為B={(b，vi)|vi∈V}，表示用戶vi的行為b，這里的用戶行為包括用戶間的跟隨行為、用戶對位置的簽到和評分等。

1.2.2 問題輸出

在給定基于位置的社交網(wǎng)絡G=(V，E，W)以及網(wǎng)絡中的用戶行為B={(b，vi)|vi∈V}的前提下，解決如下問題:

1)如何構(gòu)建網(wǎng)絡模型，解決基于位置的社交網(wǎng)絡中的鏈接預測面臨的網(wǎng)絡異構(gòu)性、權(quán)值定義不完善、未考慮時間因素等問題。通過提取時空節(jié)點，將網(wǎng)絡劃分成“時空 用戶 位置類別”四層超網(wǎng)絡，融合時間因素的影響，同時挖掘用戶的隱位置 類別”四層加權(quán)超網(wǎng)絡:GT、GU、GP、GC、WM，可以利用本文提出的方法預測用戶子網(wǎng)中用戶之間可能存在的鏈接關(guān)系E+。更明確的問題定義表示為:式行為，計算用戶間影響力，利用用戶的興趣偏好以及位置間的潛在關(guān)聯(lián)關(guān)系，量化超網(wǎng)絡中的相關(guān)邊權(quán)值，構(gòu)建四層加權(quán)超網(wǎng)絡模型 SG=(GT，GU，GP，GC，WM，B)。

2)如何利用加權(quán)超網(wǎng)絡模型進行鏈接預測，并解決網(wǎng)絡稀疏性問題。通過定義多種類型的超邊結(jié)構(gòu)可以量化用戶間不同的關(guān)聯(lián)關(guān)系，解決數(shù)據(jù)稀疏性問題，并引入?yún)?shù)集合θ，量化每種超邊結(jié)構(gòu)的重要程度，求取最優(yōu)參數(shù)集合θ+=Pθ(E|G)，利用最優(yōu)參數(shù)集合θ+對用戶間的鏈接關(guān)系E+進行預測，即E+=Pθ+(EU|GU)。

2 基于時空關(guān)系的超網(wǎng)絡鏈接預測方法

本文方法主要包括三個階段:1)構(gòu)建加權(quán)超網(wǎng)絡模型，構(gòu)建時空 用戶 位置 類別四層超網(wǎng)絡，將時間、社交、位置等因素有效融合，然后基于用戶影響力、隱關(guān)聯(lián)關(guān)系、用戶偏好以及節(jié)點度信息量化超網(wǎng)絡中的邊權(quán)值，構(gòu)建四層加權(quán)超網(wǎng)絡模型;2)建立加權(quán)超邊結(jié)構(gòu)，在加權(quán)超網(wǎng)絡模型的基礎上，建立超邊結(jié)構(gòu);3)建立超鏈接預測，對每種超邊結(jié)構(gòu)的重要程度進行量化，從而對用戶間的鏈接關(guān)系進行預測。

2.1 構(gòu)建加權(quán)超網(wǎng)絡模型

在上述定義的時空子網(wǎng)、用戶子網(wǎng)、位置子網(wǎng)以及類別子網(wǎng)的基礎上，子網(wǎng)與子網(wǎng)間也有一定的關(guān)聯(lián)，如圖1所示。通過四種不同的加權(quán)方式對子網(wǎng)內(nèi)以及子網(wǎng)間的邊權(quán)值進行定義和量化。

圖1 加權(quán)超網(wǎng)絡模型Fig.1 Weighted supernetwork model

2.1.1 基于用戶影響力

在基于位置的社交網(wǎng)絡中，每個用戶的影響力是不同的。如果某個好友對我們的影響力極低，那么我們很難通過該好友與其他人產(chǎn)生某些行為與聯(lián)系。所以，通過用戶的影響力量化用戶 用戶邊權(quán)值w(u，u')是提高模型解釋性和準確性的一種可行方法。本文主要通過挖掘基于位置的社交網(wǎng)絡中的追隨行為以及追隨網(wǎng)絡來度量用戶的影響力，如果用戶u'在其好友u簽到過的地方進行了一次簽到，則認為用戶u'產(chǎn)生了對用戶u的追隨行為。由追隨行為構(gòu)成的有向網(wǎng)絡，稱之為追隨網(wǎng)絡Gf=(Vf，Ef)，其中:Vf表示追隨網(wǎng)絡中的用戶，Ef表示追隨行為的有向邊。與此同時，我們將用戶影響力分為用戶個體影響力以及用戶間影響力，并分別通過追隨網(wǎng)絡以及追隨行為來度量。

1)用戶個體影響力。

用戶個體影響力Iu用于度量用戶因自身行為對網(wǎng)絡中其他用戶產(chǎn)生的影響，是一種全局角度的度量方法。由于個體影響力會隨著時間而動態(tài)變化，有的用戶可能開始比較活躍，其簽到行為產(chǎn)生了許多追隨邊，產(chǎn)生了較大的影響力，之后活躍度下降，則其影響力會逐漸減弱，長久如此，影響力會衰減至一個較低的穩(wěn)定值。因此，在考慮用戶影響力的時候，時間因素的影響極為重要。

本文首先劃分s個不同的時間切片，將每個時間切片中用戶的追隨行為構(gòu)成相應的追隨網(wǎng)絡(，…)，用戶的最終個體影響力由每一個時域中的個體影響力貢獻而來，并且離當前時刻越久遠的時域其個體影響力衰減越多?？紤]到網(wǎng)絡中孤立節(jié)點的存在，本文采用LeaderRank算法［16］求解用戶個體影響力。該算法通過引入Ground Node，很好地解決了PageRank中因孤立節(jié)點而造成的排序結(jié)果不唯一的問題，算法的迭代公式如下:

其中:Nu表示用戶u的鄰居節(jié)點;koutu'表示u'的出度。

在穩(wěn)定狀態(tài)下，LeaderRank將Ground Node的分數(shù)均勻分布到所有其他節(jié)點，因此節(jié)點的最終得分可以表示為:

其中:Ig(td)是Ground Node在穩(wěn)定狀態(tài)下的分數(shù);N表示用戶節(jié)點個數(shù)。

隨著時間的推移，用戶的影響力會隨之遞減，所以本文定義衰減函數(shù)為:

其中:tc表示當前時刻;ti表示第i個時間片;tm表示影響力減小的半衰期。則用戶u在當前時刻個體影響力總值Iu為:

其中Iuti表示第ti個時間片用戶u的個體影響力。

2)用戶間影響力。

用戶間影響力Ii(u，u')用于度量用戶u對用戶u'的影響力大小，是一種局部視角的度量方法。通常情況下，兩個用戶之間交互次數(shù)越多，則他們之間的影響力會越大。在本文中將追隨行為視為用戶間的交互并以此來度量用戶間影響力。提出追隨地點比例Ip和追隨簽到比例Ic這兩種衡量指標:

其中:Mu'，u表示用戶u'追隨用戶u的簽到地點數(shù);Positionu表示用戶u的簽到位置總數(shù);Ku'，u表示用戶u'追隨用戶u的總簽到次數(shù);Checkinu表示用戶u的簽到總次數(shù)。

綜合考慮用戶間影響力Ii(u，u')和用戶的個體影響力Iu，則用戶影響力I(u，u')為:

其中:Iu為用戶個體影響力;Ip為追隨地點比例;Ic為追隨簽到比例;1+2+3=1，本文中1=0.4，2=3=0.3。

基于用戶影響力，可以定義用戶 用戶邊權(quán)值w(u，u')，對于節(jié)點對u－u'，如果u'對u的用戶間影響力高，則對應權(quán)值w(u，u')也應當高，所以用戶間的邊權(quán)值為:

2.1.2 基于隱關(guān)聯(lián)關(guān)系

隱關(guān)聯(lián)關(guān)系指的是無法直接通過用戶的簽到信息觀察到的關(guān)系，例如兩個位置之間的關(guān)系以及兩個類別之間的關(guān)系。曹玖新等［17］將兩個位置之間的這種關(guān)系定義為興趣點相關(guān)，本文中的位置 位置邊權(quán)值是在此定義的上進行改進的。

1)位置 位置邊權(quán)值w(p，p')。

如果某個用戶在一定的時間閾值內(nèi)連續(xù)訪問了某兩個位置，那么這兩個位置就存在一定的隱含關(guān)聯(lián)關(guān)系，同時由于大多數(shù)用戶喜歡訪問與曾經(jīng)去過的位置相近的位置［18］，所以本文通過距離以及隱含關(guān)聯(lián)關(guān)系定義位置與位置之間的邊權(quán)值:

其中:geodist(p，p')表示位置p和p'間的距離;Countp表示所有被關(guān)聯(lián)位置次數(shù)的最大值;Count(p，p')表示兩個位置被關(guān)聯(lián)的次數(shù)。

2)時空 時空邊權(quán)值w(t，t')。

時空節(jié)點之間的邊權(quán)值是在位置邊權(quán)值的基礎上增加時間距離，其定義如下:

3)類別 類別邊權(quán)值w(c，c')。

如果兩種類別屬性同時出現(xiàn)在多個位置，那么這兩種類別之間也就存在一定的隱含關(guān)聯(lián)關(guān)系，例如從數(shù)據(jù)統(tǒng)計中可以發(fā)現(xiàn)類別Bars與類別Nightlife經(jīng)常出現(xiàn)在多個位置的類別屬性中，隱含地表明這兩種類別之間存在一定的相關(guān)性。本文通過這種相關(guān)性定義類別 類別邊權(quán)值:

其中:Count(c，c')表示同時屬于類別c和類別c'的地點個數(shù);Countc表示同時屬于類型c和其他某種類型的地點數(shù)的最大值。

2.1.3 基于用戶偏好

用戶偏好反映了用戶對位置的喜好程度，如果兩個用戶對同一個興趣點表現(xiàn)出濃厚的興趣，那么這兩個用戶有很大的可能會產(chǎn)生鏈接關(guān)系，所以為了有效融入偏好信息，提高超網(wǎng)絡模型的可解釋性，本文從用戶評分入手定義和量化用戶位置邊權(quán)值w(u，p)以及用戶 時空邊權(quán)值w(u，t)。

在基于位置的社交網(wǎng)絡中，用戶對位置的評分屬性能夠直觀地反映出用戶對這個位置的偏好程度。比如，用戶u1在p1、p2、p3三個位置進行過評分，并分別給出了5、3、1的評分值，如果不考慮用戶對這個位置的評分屬性，那么會給每條用戶 位置邊賦值1/3，但實際上這是不準確的，如果用戶u1對p3的評分為1分，表明用戶對這個地方是不滿意的，這個時候，應當增加u1－p1的邊權(quán)值，減小u1－p3的邊權(quán)值。因此，應當給用戶偏好高的位置更高的權(quán)值，本文參考文獻［19］的方法通過指數(shù)函數(shù)定義用戶 位置邊權(quán)值，計算式如下:

其中r(u，p)表示用戶u在位置p處的評分。

基于同樣的道理，用戶 時空邊權(quán)值也可以相應地通過指數(shù)函數(shù)進行定義，計算式如下:

其中r(u，t)表示用戶u在時空節(jié)點t處的評分。

需要注意的是如果用戶對一個位置進行過多次評分，本文僅將用戶的最后一次的評分作為標準。

2.1.4 基于節(jié)點度信息

通過節(jié)點度信息定義和量化邊權(quán)值類似于資源分配的原理，如果節(jié)點出度較多，則每個出度節(jié)點獲得的資源就會相對較少。

1)時空 用戶邊權(quán)值w(t，u):

其中|Ut|表示時空節(jié)點包含的用戶個數(shù)。

2)位置 用戶邊權(quán)值w(p，u):

3)位置 類別邊權(quán)值w(p，c):

其中|Cp|表示位置p所屬的類別個數(shù)。

4)類別 位置邊權(quán)值w(c，p):

其中|Pc|表示類別c包含的位置個數(shù)。

2.2 建立加權(quán)超邊結(jié)構(gòu)

2.2.1 加權(quán)超邊結(jié)構(gòu)相關(guān)定義

在加權(quán)超網(wǎng)絡模型中，存在著多種類型的超邊，比如用戶節(jié)點與位置節(jié)點間構(gòu)成的邊可稱為一條超邊，用戶節(jié)點與時空節(jié)點間構(gòu)成的邊也可稱為一條超邊。由于不同的超邊，其包含的異構(gòu)節(jié)點個數(shù)不同，因此，定義三種類型的超邊。

定義5 一類超邊SEI。一類超邊是指只包含一種類型節(jié)點的超邊，在超網(wǎng)中屬于一類特殊的超邊。例如，兩個用戶節(jié)點構(gòu)成的一條超邊稱之為一類超邊。一類超邊表明了同層子網(wǎng)中節(jié)點之間的關(guān)聯(lián)關(guān)系，例如對于用戶子網(wǎng)，指的是用戶之間的好友關(guān)系。

定義6 二類超邊SEII。二類超邊是指相鄰兩層子網(wǎng)之間的節(jié)點對構(gòu)成的邊，其特點是只包含兩種異構(gòu)節(jié)點。例如，用戶與位置節(jié)點或者用戶與時空節(jié)點之間構(gòu)成的超邊，稱之為二類超邊。

定義7 三類超邊SEIII。三類超邊是指相鄰三層子網(wǎng)構(gòu)成的邊，其特點是包含三種異構(gòu)節(jié)點。例如，用戶、位置和類別節(jié)點構(gòu)成的超邊，稱之為三類超邊。

如圖2～3所示，圖2為相鄰的兩層網(wǎng)絡，其中:(t1－t2)構(gòu)成了一條一類超邊，記為SEI(t1－t2);(u1－t1)構(gòu)成了一條二類超邊，記為SEII(u1－t1);(u3－t1)也構(gòu)成了一條二類超邊，記為SEII(u3－t1)。圖3為相鄰的三層網(wǎng)絡，其中:(u1－p1－c1)組成了一條三類超邊，記為SEIII(u1－p1－c1)，(c1－p3－u3)也組成了一條三類超邊，記為SEIII(c1－p3－u3)。

圖2 二層超網(wǎng)絡Fig.2 Two-layer supernetwork

圖3 三層超網(wǎng)絡Fig.3 Three-layer supernetwork

定義8 超邊權(quán)重。超邊權(quán)重是指每條超邊所具有的權(quán)值，可通過超邊中包含的邊權(quán)值計算得到。例如，圖2中的二類超邊SEII(u1－t1)，其超邊權(quán)重WSEII(u1－t1)=w(u1，t1);圖3中的三類超邊權(quán)重WSEIII(u1－p1－c1) =w(u1，p1)·w(p1，c1)，WSEIII(c1－ p3－ u3)=w(c1，p3)·w(p3，u3)。

基于這三種類型的超邊，本文提出加權(quán)超邊結(jié)構(gòu)，通過加權(quán)超邊結(jié)構(gòu)解決用戶與用戶間的超鏈接預測問題。在以往的方法中，主要是通過加權(quán)超三角形結(jié)構(gòu)來計算節(jié)點之間的關(guān)聯(lián)程度，其主要思想是通過不同超邊之間的共現(xiàn)節(jié)點將兩條超邊關(guān)聯(lián)起來，從而得到超三角形結(jié)構(gòu)用于度量節(jié)點間的相似性。這種方法適用于異構(gòu)網(wǎng)絡，能夠簡單高效地捕捉兩個節(jié)點之間的額外關(guān)聯(lián)，在緩解數(shù)據(jù)稀疏問題的同時也提高了預測準確度。然而超網(wǎng)絡不僅可以描述同構(gòu)節(jié)點之間的關(guān)聯(lián)，同時能夠描述異構(gòu)節(jié)點之間的關(guān)聯(lián)，因此考慮的網(wǎng)絡層次越深，關(guān)聯(lián)鏈越長，則越可以反映出節(jié)點間細粒度的隱性關(guān)聯(lián)。本文通過構(gòu)造多種類型的加權(quán)超邊結(jié)構(gòu)挖掘節(jié)點間的隱含語義關(guān)系。

在本文的方法中主要包含三類加權(quán)超邊結(jié)構(gòu)，分別為加權(quán)超三角形結(jié)構(gòu)、加權(quán)超矩形結(jié)構(gòu)以及加權(quán)超混合結(jié)構(gòu)。下面通過圖2～3對這三類結(jié)構(gòu)進行舉例說明。

2.2.2 加權(quán)超三角形結(jié)構(gòu)

1)單加權(quán)超三角形結(jié)構(gòu)。

如圖2所示，可以通過時空節(jié)點t1與用戶節(jié)點u1、u3構(gòu)成的單層加權(quán)超三角形結(jié)構(gòu)來計算u1、u3間的相似性。如果包含u1、u3的單加權(quán)超三角形結(jié)構(gòu)個數(shù)越多，權(quán)值越大，則認為它們之間的關(guān)聯(lián)性也越大，越可能產(chǎn)生鏈接。該超三角形結(jié)構(gòu)包含兩條二類超邊SEII(u1－t1)和SEII(t1－u3)，超三角形結(jié)構(gòu)的權(quán)重為對應超邊權(quán)重之積，計算式如下:

需要強調(diào)的是本文定義的超邊結(jié)構(gòu)均為閉環(huán)結(jié)構(gòu)，具有方向性，所以WS3(u1u3)≠WS3(u3u1)，后文同理。

2)雙加權(quán)超三角形結(jié)構(gòu)。

雙加權(quán)超三角形結(jié)構(gòu)包含兩個連續(xù)的單加權(quán)超三角形結(jié)構(gòu)，例如，圖2中SEII(u1－t1)和SEII(t1－u2)組成了一個單加權(quán)超三角形結(jié)構(gòu)WS3(u1u2)，SEII(u2－t2)和SEII(t2－u3)也構(gòu)成了一個單加權(quán)超三角形結(jié)構(gòu)WS3(u2u3)，這兩個單加權(quán)超三角形結(jié)構(gòu)可以組合成一個雙加權(quán)超三角形結(jié)構(gòu)，用來度量u1、u3之間的相似度，該結(jié)構(gòu)的語義信息為用戶u1和u3都喜歡與用戶u2在相同時間相同的位置活動。該雙加權(quán)超三角形結(jié)構(gòu)權(quán)值為對應的兩個單加權(quán)超三角形結(jié)構(gòu)權(quán)值之積，所以權(quán)值為:

3)三層加權(quán)超三角形結(jié)構(gòu)。

三層加權(quán)超三角形結(jié)構(gòu)是指由兩條三類超邊組成的三角形結(jié)構(gòu)。如圖3所示，超邊 SEIII(u1－p1－c1)和超邊SEIII(u1－p3－c3)就組成了一個三層加權(quán)超三角形結(jié)構(gòu)。其權(quán)值為兩條三類超邊權(quán)值之積，所以權(quán)值為:

2.2.3 加權(quán)超矩形結(jié)構(gòu)

如圖2所示，超邊 SEII(u1－t1)，SEI(t1－t2)，SEII(t2－u3)可以構(gòu)成一個加權(quán)超矩形結(jié)構(gòu)，該加權(quán)超矩形結(jié)構(gòu)中包含了u1、u3兩個節(jié)點，可用于度量u1、u3之間的相似性，該結(jié)構(gòu)的語義信息為用戶u1和u3喜歡在兩個相關(guān)的時空節(jié)點處活動，其權(quán)值為對應超邊權(quán)值之積，所以權(quán)值為:

2.2.4 加權(quán)超混合結(jié)構(gòu)

1)加權(quán)超混合I結(jié)構(gòu)。

混合I結(jié)構(gòu)是指在單三角形結(jié)構(gòu)的基礎上增加一條一類超邊而組成的結(jié)構(gòu)。如圖2所示，由超邊SEII(u1－t1)，SEII(t1－u2)，SEI(u2－u3)組成的結(jié)構(gòu)屬于混合I結(jié)構(gòu)，該結(jié)構(gòu)表達的語義信息為u3的好友u2喜歡與u1在相同的時間相同的位置活動，其權(quán)值為對應的單加權(quán)超三角形結(jié)構(gòu)權(quán)值與一類超邊權(quán)值之積，計算式如下:

2)加權(quán)超混合II結(jié)構(gòu)。

混合II結(jié)構(gòu)是指在矩形結(jié)構(gòu)的基礎上增加一條一類超邊而組成的結(jié)構(gòu)。如圖2所示，由超邊SEII(u1－t1)，SEI(t1－t2)，SEII(t2－u2)，SEI(u2－u3)組成的結(jié)構(gòu)屬于混合II結(jié)構(gòu)，其權(quán)值為對應的加權(quán)超矩形結(jié)構(gòu)權(quán)值與一類超邊權(quán)值之積，計算式如下:

可以看出層次越深，關(guān)聯(lián)鏈路越長，超邊結(jié)構(gòu)越豐富。本文列出了其中19種加權(quán)超邊結(jié)構(gòu)，如表1所示。

從前文分析可知，不同的加權(quán)超邊結(jié)構(gòu)具有不同的語義信息，例如S2結(jié)構(gòu)體現(xiàn)了位置熵［20］的含義，位置熵是指如果兩個用戶在一個很多人去過的地方有過共同簽到，很難預測這兩個人之間存在好友關(guān)系，因為這有可能是一種巧合，但是如果兩個用戶經(jīng)常在一個很少人去過的地方進行簽到，則表明它們之間很可能存在一定的關(guān)系。所以一個位置的受歡迎程度也對鏈接預測有著影響，而通過S2結(jié)構(gòu)能夠有效捕捉到這種影響。S3結(jié)構(gòu)能夠挖掘出用戶的一種短期興趣，此處的短期興趣解釋為用戶可能只在某一個時間段才具有的興趣，例如每周五晚上7點去電影院看電影。這種興趣只會發(fā)生在特定的時間段，但更能體現(xiàn)出用戶的個性。S11結(jié)構(gòu)反映了兩個用戶雖然沒有去過同一個位置，但卻經(jīng)常去相同類別的地方，這體現(xiàn)了兩個用戶擁有相同的類別偏好，有助于挖掘用戶間的關(guān)聯(lián)關(guān)系。

2.3 超鏈接預測

對于訓練集中任意兩個用戶(u，v)，均存在上述的19種加權(quán)超邊結(jié)構(gòu)特征，這些特征的集合可以表示為W(u，v)={WS1(u，v)，WS2(u，v)，…，WS19(u，v)}。本文通過邏輯回歸計算u對v產(chǎn)生鏈接的概率:

其中θi表示第i個加權(quán)超邊結(jié)構(gòu)對鏈接建立的影響程度，利用梯度下降算法來更新參數(shù)值，參數(shù)更新過程如下:

其中:λ表示學習步長;yu－v表示用戶間是否存在鏈接。當每個參數(shù)的變化值都小于某個閾值時，參數(shù)更新已收斂，得到最優(yōu)參數(shù)集合θ+。

最終對于測試集中的用戶對(u，u')，其產(chǎn)生鏈接的概率為:

當 P(yu－u'～ W) 大于等于閾值 ξ時，yu－u'取值為 1，認為用戶間存在鏈接;否則yu－u'取值為0，認為用戶間不存在鏈接。從而找出了用戶間可能存在的鏈接關(guān)系E+。yu－u'定義式如下:

2.4 算法描述

本文輸入為基于位置的社交網(wǎng)絡G=(V，E，W)以及網(wǎng)絡中的用戶行為B={(b，vi)|vi∈V}，輸出為用戶子網(wǎng)中的可能存在的鏈接關(guān)系E+。通過構(gòu)建加權(quán)超網(wǎng)絡模型，建立多種加權(quán)超邊結(jié)構(gòu)計算用戶節(jié)點之間產(chǎn)生鏈接的概率，從而預測用戶間可能存在的鏈接關(guān)系。其算法描述如算法1所示。

算法1 基于時空關(guān)系的超網(wǎng)絡鏈接預測方法。

輸入 基于位置的社交網(wǎng)絡G=(V，E，W);網(wǎng)絡中的用戶行為 B={(b，vi)|vi∈ V}。

輸出 用戶子網(wǎng)中可能存在的鏈接關(guān)系E+。

//劃分四層超網(wǎng)絡

1) 基于用戶的簽到位置p和時間time構(gòu)建時空節(jié)點T;

2) 構(gòu)建時空子網(wǎng)GT、用戶子網(wǎng)GU、位置子網(wǎng)GP和類別子網(wǎng)GC;

3) 基于用戶影響力、隱關(guān)聯(lián)關(guān)系、用戶偏好以及節(jié)點度信息定義網(wǎng)絡邊權(quán)值，并依據(jù)式(1)～(17)對網(wǎng)絡邊權(quán)值進行量化;

4) 構(gòu)建三種類型的超邊SEI、SEII、SEIII，并計算超邊權(quán)重WSE;

5) 基于三類超邊，建立加權(quán)超三角形結(jié)構(gòu)、加權(quán)超矩形結(jié)構(gòu)、加權(quán)超混合結(jié)構(gòu)，并依據(jù)式(18)～(23)計算加權(quán)超邊結(jié)構(gòu)的權(quán)重WSi;

6) For j←1 to|M|do //|M|為總節(jié)點對個數(shù)

7) For i←1 to 19 do //19種超邊結(jié)構(gòu)

8) 計算每一個超邊結(jié)構(gòu)下的WSi;

9) End for

10) 依據(jù)式(24)計算鏈接產(chǎn)生概率，并加入候選集合Ms;

11)End for

12)根據(jù)式(26)計算Ms集合中的P(yu－u'～W);

13)根據(jù)式(27)判斷用戶間可能存在的鏈接關(guān)系E+。

3 仿真實驗與分析

3.1 數(shù)據(jù)集

本文采用yelp數(shù)據(jù)集進行實驗，數(shù)據(jù)集來源于yelp挑戰(zhàn)賽的開放數(shù)據(jù)集，包含了用戶表、商家表以及評論表。用戶表中有每個用戶的好友列表、評論次數(shù)等信息，商家表中有所屬類別、經(jīng)緯度以及一些詳細的屬性標簽。評論表中有用戶對商家的評論、評分以及評分時間。

實驗中，刪除總評論數(shù)少于10次的不活躍用戶以及被評論總次數(shù)少于5次的商家以減小稀疏數(shù)據(jù)的影響，處理后的用戶簽到分布以及商家被簽到分布情況如圖4所示。圖4(a)中橫坐標為20的坐標點表示用戶簽到次數(shù)在［10，20)的用戶數(shù)。從圖4可以看出用戶簽到以及商家被簽到次數(shù)均符合冪律分布特性。

圖4 用戶和商家簽到分布Fig.4 Check-in distribution of users and businesses

接下來對預處理后各層子網(wǎng)以及相鄰子網(wǎng)間的情況進行統(tǒng)計說明。

1)四層子網(wǎng)。針對時空子網(wǎng)，由于yelp數(shù)據(jù)集中評論時間只能精確到天，考慮到相隔時間太長會影響時空節(jié)點的本質(zhì)作用，所以本文以同一天為標準提取時空節(jié)點，實驗中總共提取的時空節(jié)點個數(shù)為850 437個，所以該層節(jié)點數(shù)為850437個，理論上任意兩個時空節(jié)點之間均存在連邊(通過權(quán)值控制連邊強弱);針對用戶子網(wǎng)，由于剔除了總評論次數(shù)少于10次的不活躍用戶，所以該層保留的有效節(jié)點數(shù)為426656個，相比于原始用戶數(shù)據(jù)占比0.414，好友關(guān)系數(shù)為2703594條，相比于原始用戶關(guān)系占比0.461;針對位置子網(wǎng)，由于剔除了被評論次數(shù)少于5次的商家，所以該層的剩余節(jié)點數(shù)為95190個，相比于原始商家數(shù)占比為0.661，理論上任意兩個商家位置之間均存在連邊;針對類別子網(wǎng)，由于部分商家被踢除，導致總體類別數(shù)下降，由原來的1192類商家減少到1007類，所以該層的節(jié)點個數(shù)為1007個，相比于原始類別數(shù)據(jù)占比為0.845，理論上任意兩個類別節(jié)點之間均存在連邊。

2)相鄰子網(wǎng)。由于剔除了部分用戶以及商家，使得用戶 位置邊減少(評論簽到關(guān)系)，由原來的4 153 150條邊較少為2943312條邊，占比為0.709;用戶 時空節(jié)點之間的邊數(shù)統(tǒng)計為4295 788條，從數(shù)據(jù)統(tǒng)計結(jié)果可以看出，對于大多數(shù)時空節(jié)點來說，僅包含兩個用戶，隨著時空節(jié)點包含用戶數(shù)的增多，相應時空節(jié)點個數(shù)按冪律分布減少，如圖5所示，位置 類別之間的邊數(shù)統(tǒng)計為351952條。

3.2 評價指標

本文中，主要使用準確率(precision)、召回率(recall)、F1指標(F1-measure)、受試者工作特征曲線下面積(Area Under the receiver operating characteristic Curve，AUC)來評估算法的質(zhì)量。

圖5 時空節(jié)點分布Fig.5 Distribution of spatio-temporal nodes

4)AUC。

AUC是評估鏈接預測結(jié)果質(zhì)量的常用指標。AUC指標可以描述為在測試集中隨機選擇一條存在連邊的分數(shù)值比隨機選擇一條不存在連邊的分數(shù)值高的概率。這樣獨立重復比較n次，在n次中，如果有n'次在測試集中存在連邊的分數(shù)比不存在連邊的分數(shù)值高，有n″次在測試集中存在連邊的分數(shù)值與不存在連邊的分數(shù)值相等，則AUC值可以定義為:

一般來說，AUC值越高代表預測性能越好，完美結(jié)果的AUC值是1.0，而隨機預測結(jié)果的AUC是0.5。

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

在實驗中，采用不同的比例(0.5～0.9)來劃分數(shù)據(jù)集以準確評估算法的性能。首先對比不同超邊結(jié)構(gòu)及其組合下的準確率、召回率、F1值以及AUC。令:K1表示加權(quán)超三角形結(jié)構(gòu)，K2表示加權(quán)超矩形結(jié)構(gòu)，K3表示加權(quán)超混合結(jié)構(gòu)。

實驗結(jié)果如圖6所示，其中橫坐標表示訓練集占整個數(shù)據(jù)集的比例。從圖6可以看出，隨著訓練集邊數(shù)占總邊數(shù)的比例加大，所有指標均呈現(xiàn)上升狀態(tài)，表明預測的效果在不斷提升。從圖6(d)中AUC指標可以看出，訓練集占比為0.9時，各特征的預測性能達到最優(yōu)。其中:K1的預測效果是最好的，其次是K3，最后是K2。其原因是K1結(jié)構(gòu)能夠捕捉到較多重要的信息，比如，其中的S1結(jié)構(gòu)能夠捕捉兩個用戶的共同好友信息，S2結(jié)構(gòu)能夠捕捉兩個用戶的共同簽到地點信息，S3結(jié)構(gòu)能夠捕捉兩個用戶的共同時空節(jié)點信息，而這些都是預測用戶之間鏈接較為重要的信息。

在兩兩組合的預測效果中，K2+K3的預測性能最差，預測效果低于K1特征，K1+K3的預測性能最好，可以看出組合

1)準確率。

令VL為得分最高的L個節(jié)點對，如果在VL中只有m個節(jié)點對存在連邊，則準確度可以表示為:

2)召回率。

令M=|E|，表示網(wǎng)絡中存在的邊，假設算法預測出來的缺失邊個數(shù)為m，則召回率可通過如式(29)求得:

3)F1指標。

通過準確率和召回率，可以得到F1綜合指標，其定義如下:特征的效果要優(yōu)于組合中單個特征的效果。K1+K2+K3由于 有效融合了每組結(jié)構(gòu)特征的信息，所以其預測性能最優(yōu)。

圖6 不同特征組合下各指標對比Fig.6 Comparison of different indicators under different combinations of features

由于訓練集占比為0.9時，算法性能最優(yōu)，所以后面的對比實驗均采用0.9來劃分數(shù)據(jù)集。為了驗證時空節(jié)點的引入對實驗結(jié)果的影響，本文對比包含時空節(jié)點層的加權(quán)超網(wǎng)絡模型與不包含時空節(jié)點層的加權(quán)超網(wǎng)絡模型(用戶 位置 類別三層)，并分別提取模型中的加權(quán)超邊結(jié)構(gòu)，計算節(jié)點間的相似性，實驗結(jié)果如圖7所示，其中橫坐標表示不同的指標，縱坐標表示這些指標下的測試值。

圖7 時空節(jié)點對比Fig.7 Comparison of spatio-temporal nodes

從圖7中可以看出，引入時空節(jié)點層之后，算法的準確率、召回率、F1值以及AUC都有一定程度的提升，其原因是時空節(jié)點不僅能夠捕捉兩個用戶在訪問位置上的興趣相似性，同時還能捕捉其在訪問時間上的相似性。因此，即使兩個用戶共同簽到位置數(shù)較少，但只要他們在這些地方的簽到時間比較接近，也能夠通過時空節(jié)點層準確捕捉他們之間的相似性，從而對鏈接關(guān)系進行有效預測，而這些是無法通過位置節(jié)點做到的。時空節(jié)點層的引入使得我們可以兼顧位置因素的影響以及時空因素的影響，通過對這兩類信息的有效利用，本文的算法性能得到了一定的提升。

最后對比不同方法之間的性能優(yōu)劣，本文選取同構(gòu)網(wǎng)絡中的方法以及異構(gòu)網(wǎng)絡中的方法與本文的方法進行對比。同構(gòu)網(wǎng)絡中的對比方法選擇經(jīng)典的共同鄰居指標 (Common Neighbor，CN)［21］、資 源 分 配 指 標 (Resource Allocation，RA)［22］，其中 CN 是由 Liben-Nowell等［21］提出的解決鏈接預測問題的基本方法，是一種基于鄰居結(jié)構(gòu)的標準度量方法;RA則是由Zhou等［22］在CN的基礎上提出的改進方法，并驗證了其在多個網(wǎng)絡中的有效性，這兩種方法屬于同構(gòu)網(wǎng)絡中解決鏈接預測問題的代表性方法。異構(gòu)網(wǎng)絡中選擇文獻［8］中的方法Model-II、文獻［12］中的超鏈接預測方法超網(wǎng)絡杰卡德指標(Supernetwork JACCARD，SJACCARD)，以及文獻［13］中的PathPredict方法，其中Model-II方法基于兩個用戶所有的共現(xiàn)位置信息提出了五種相關(guān)特征:加權(quán)共現(xiàn)次數(shù)、加權(quán)共同位置數(shù)、平均時間間隔、最小時間間隔、最大時間間隔，并驗證了算法的優(yōu)越性;SJACCARD方法為加權(quán)超網(wǎng)絡下的一種方法，該方法通過加權(quán)超三角結(jié)構(gòu)預測節(jié)點之間的鏈接關(guān)系，取得了一定的效果;PathPredict方法為異構(gòu)網(wǎng)絡鏈接預測中的基準方法，該方法通過路徑數(shù)、隨機游走等方式度量異質(zhì)節(jié)點之間的語義關(guān)聯(lián)關(guān)系，適用于無權(quán)網(wǎng)絡。本文所有結(jié)果均采用10折交叉驗證得到，六種方法的性能對比結(jié)果如表2所示。

由表2可以看出，所有的異構(gòu)方法均要優(yōu)于同構(gòu)方法，反映出異構(gòu)方法對信息的利用率更高。CN和RA方法僅僅利用到了同構(gòu)網(wǎng)絡中的社交關(guān)系，所以其各指標均相對較低，RA方法由于通過節(jié)點的度信息量化了不同鄰居節(jié)點的貢獻，所以其性能要優(yōu)于CN。在異構(gòu)方法中由于SJACCARD方法僅僅利用到了兩種異構(gòu)加權(quán)超三角形結(jié)構(gòu)，未能利用到同構(gòu)邊關(guān)系，所以其AUC值僅比CN高出0.049，PathPredict方法雖然通過多種元路徑特征較好地捕捉了異構(gòu)關(guān)系，但其沒能有效利用網(wǎng)絡中的多種權(quán)值信息，所以其AUC值低于本文方法，但高出 CN方法0.154，Model-II方法的性能優(yōu)于PathPredict，AUC值達到了0.915，較好地證明了時間因素的引入能夠提高預測精度。本文方法通過引入時空節(jié)點以及多種異構(gòu)結(jié)構(gòu)，同時較好地結(jié)合了網(wǎng)絡邊權(quán)值，預測性能最優(yōu)，AUC值達到0.958，相比于異構(gòu)網(wǎng)絡方法中的Model-II方法，AUC值提升了4.69%。

表2 不同方法的性能對比Tab.2 Performance comparison of different methods

4 結(jié)語

鏈接預測研究可以用于解決網(wǎng)絡中的鏈路缺失問題，在推薦領域具有重要的應用前景。針對LBSN鏈接預測中網(wǎng)絡權(quán)值利用不完善以及數(shù)據(jù)稀疏性等問題，本文提出了一種可行方法。該方法通過用戶影響力、隱關(guān)聯(lián)關(guān)系、用戶偏好以及節(jié)點度信息對超網(wǎng)絡中的邊權(quán)值進行定義和量化，并通過多種加權(quán)超邊結(jié)構(gòu)來捕捉用戶間的多種關(guān)聯(lián)關(guān)系，緩解數(shù)據(jù)稀疏性問題的同時提高了鏈接預測性能。實驗結(jié)果表明，本文方法相比現(xiàn)有其他方法有著更加準確的預測精度，更加適用于復雜的異構(gòu)網(wǎng)絡推薦領域，可提高用戶對平臺的忠誠度以及黏度，從而令平臺具備更加長久的發(fā)展空間。

本文僅針對一個社交網(wǎng)絡數(shù)據(jù)進行研究，而大多數(shù)用戶會活躍在多個社交平臺，例如QQ和微博，如何獲取相應數(shù)據(jù)并合理構(gòu)建多維度的超網(wǎng)絡模型來預測網(wǎng)絡中的連邊關(guān)系是我們下一步要解決的關(guān)鍵問題。