基于位置的社交網(wǎng)絡(luò)中基于時(shí)空關(guān)系的超網(wǎng)絡(luò)鏈接預(yù)測(cè)方法

胡 敏，陳元會(huì)，黃宏程

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

0 引言

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

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

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

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

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

本文的主要工作如下:

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

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

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

1 問(wèn)題定義

1.1 相關(guān)定義

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

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

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

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

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

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

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

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

1.2 問(wèn)題形式化

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

1.2.1 問(wèn)題輸入

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

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

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

1.2.2 問(wèn)題輸出

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

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

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

2 基于時(shí)空關(guān)系的超網(wǎng)絡(luò)鏈接預(yù)測(cè)方法

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

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

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

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

2.1.1 基于用戶(hù)影響力

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

1)用戶(hù)個(gè)體影響力。

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

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

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

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

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

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

其中:tc表示當(dāng)前時(shí)刻;ti表示第i個(gè)時(shí)間片;tm表示影響力減小的半衰期。則用戶(hù)u在當(dāng)前時(shí)刻個(gè)體影響力總值Iu為:

其中Iuti表示第ti個(gè)時(shí)間片用戶(hù)u的個(gè)體影響力。

2)用戶(hù)間影響力。

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

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

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

其中:Iu為用戶(hù)個(gè)體影響力;Ip為追隨地點(diǎn)比例;Ic為追隨簽到比例;1+2+3=1，本文中1=0.4，2=3=0.3。

基于用戶(hù)影響力，可以定義用戶(hù) 用戶(hù)邊權(quán)值w(u，u')，對(duì)于節(jié)點(diǎn)對(duì)u－u'，如果u'對(duì)u的用戶(hù)間影響力高，則對(duì)應(yīng)權(quán)值w(u，u')也應(yīng)當(dāng)高，所以用戶(hù)間的邊權(quán)值為:

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

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

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

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

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

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

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

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

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

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

2.1.3 基于用戶(hù)偏好

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

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

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

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

其中r(u，t)表示用戶(hù)u在時(shí)空節(jié)點(diǎn)t處的評(píng)分。

需要注意的是如果用戶(hù)對(duì)一個(gè)位置進(jìn)行過(guò)多次評(píng)分，本文僅將用戶(hù)的最后一次的評(píng)分作為標(biāo)準(zhǔn)。

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

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

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

其中|Ut|表示時(shí)空節(jié)點(diǎn)包含的用戶(hù)個(gè)數(shù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

需要強(qiáng)調(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)包含兩個(gè)連續(xù)的單加權(quán)超三角形結(jié)構(gòu)，例如，圖2中SEII(u1－t1)和SEII(t1－u2)組成了一個(gè)單加權(quán)超三角形結(jié)構(gòu)WS3(u1u2)，SEII(u2－t2)和SEII(t2－u3)也構(gòu)成了一個(gè)單加權(quán)超三角形結(jié)構(gòu)WS3(u2u3)，這兩個(gè)單加權(quán)超三角形結(jié)構(gòu)可以組合成一個(gè)雙加權(quán)超三角形結(jié)構(gòu)，用來(lái)度量u1、u3之間的相似度，該結(jié)構(gòu)的語(yǔ)義信息為用戶(hù)u1和u3都喜歡與用戶(hù)u2在相同時(shí)間相同的位置活動(dòng)。該雙加權(quán)超三角形結(jié)構(gòu)權(quán)值為對(duì)應(yīng)的兩個(gè)單加權(quán)超三角形結(jié)構(gòu)權(quán)值之積，所以權(quán)值為:

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

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

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

如圖2所示，超邊 SEII(u1－t1)，SEI(t1－t2)，SEII(t2－u3)可以構(gòu)成一個(gè)加權(quán)超矩形結(jié)構(gòu)，該加權(quán)超矩形結(jié)構(gòu)中包含了u1、u3兩個(gè)節(jié)點(diǎn)，可用于度量u1、u3之間的相似性，該結(jié)構(gòu)的語(yǔ)義信息為用戶(hù)u1和u3喜歡在兩個(gè)相關(guān)的時(shí)空節(jié)點(diǎn)處活動(dòng)，其權(quán)值為對(duì)應(yīng)超邊權(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)的基礎(chǔ)上增加一條一類(lèi)超邊而組成的結(jié)構(gòu)。如圖2所示，由超邊SEII(u1－t1)，SEII(t1－u2)，SEI(u2－u3)組成的結(jié)構(gòu)屬于混合I結(jié)構(gòu)，該結(jié)構(gòu)表達(dá)的語(yǔ)義信息為u3的好友u2喜歡與u1在相同的時(shí)間相同的位置活動(dòng)，其權(quán)值為對(duì)應(yīng)的單加權(quán)超三角形結(jié)構(gòu)權(quán)值與一類(lèi)超邊權(quán)值之積，計(jì)算式如下:

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

混合II結(jié)構(gòu)是指在矩形結(jié)構(gòu)的基礎(chǔ)上增加一條一類(lèi)超邊而組成的結(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)值為對(duì)應(yīng)的加權(quán)超矩形結(jié)構(gòu)權(quán)值與一類(lèi)超邊權(quán)值之積，計(jì)算式如下:

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

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

2.3 超鏈接預(yù)測(cè)

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

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

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

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

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

2.4 算法描述

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

算法1 基于時(shí)空關(guān)系的超網(wǎng)絡(luò)鏈接預(yù)測(cè)方法。

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

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

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

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

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

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

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

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

6) For j←1 to|M|do //|M|為總節(jié)點(diǎn)對(duì)個(gè)數(shù)

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

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

9) End for

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

11)End for

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

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

3 仿真實(shí)驗(yàn)與分析

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

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

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

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

接下來(lái)對(duì)預(yù)處理后各層子網(wǎng)以及相鄰子網(wǎng)間的情況進(jìn)行統(tǒng)計(jì)說(shuō)明。

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

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

3.2 評(píng)價(jià)指標(biāo)

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

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

4)AUC。

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

一般來(lái)說(shuō)，AUC值越高代表預(yù)測(cè)性能越好，完美結(jié)果的AUC值是1.0，而隨機(jī)預(yù)測(cè)結(jié)果的AUC是0.5。

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

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

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

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

1)準(zhǔn)確率。

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

2)召回率。

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

3)F1指標(biāo)。

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

圖6 不同特征組合下各指標(biāo)對(duì)比Fig.6 Comparison of different indicators under different combinations of features

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

圖7 時(shí)空節(jié)點(diǎn)對(duì)比Fig.7 Comparison of spatio-temporal nodes

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

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

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

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

4 結(jié)語(yǔ)

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

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