基于社交網(wǎng)絡(luò)和地理位置的用戶(hù)關(guān)系預(yù)測(cè)

杜翠鳳+陳少權(quán)

【摘 要】為了解決社交網(wǎng)絡(luò)用戶(hù)關(guān)系預(yù)測(cè)的不精確問(wèn)題，通過(guò)采用時(shí)空分析方法對(duì)移動(dòng)通信用戶(hù)的軌跡和通話(huà)關(guān)系數(shù)據(jù)進(jìn)行分析，研究了結(jié)合地理和時(shí)間的重合度以及基于用戶(hù)時(shí)空特征權(quán)重賦值算法，并提出了基于社交網(wǎng)絡(luò)和地理位置相似度的用戶(hù)關(guān)系預(yù)測(cè)方案。經(jīng)過(guò)實(shí)驗(yàn)證明，提出的算法能夠改善社交網(wǎng)絡(luò)預(yù)測(cè)的精度。

【關(guān)鍵詞】社交網(wǎng)絡(luò) 地理位置 用戶(hù)關(guān)系 相似度

doi：10.3969/j.issn.1006-1010.2017.08.004 中圖分類(lèi)號(hào)：TP391.4 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-1010（2017）08-0021-03

引用格式：杜翠鳳，陳少權(quán). 基于社交網(wǎng)絡(luò)和地理位置的用戶(hù)關(guān)系預(yù)測(cè)[J]. 移動(dòng)通信， 2017，41（8）： 21-23.

The Prediction of User Relationship

Based on Social Network and Geographic Location

DU Cuifeng， CHEN Shaoquan

[Abstract] In order to solve the problem of inaccurate prediction of the user relationship in social networks， the trajectory of mobile user and communication relation data were analyzed based on time-space analysis method. The weight assignment algorithm combined with the geographical and temporal consistency and users temporal-spatial characteristics was investigated. A prediction scheme on user relationship based on the similarity of the social network and geographical location was proposed. Experiments demonstrate that the proposed algorithm can improve the prediction accuracy of social networks.

[Key words]social network geographical location user relationship similarity

1 引言

隨著移動(dòng)應(yīng)用的發(fā)展，以QQ、微信為代表的基于社交網(wǎng)絡(luò)和位置融合的移動(dòng)應(yīng)用已經(jīng)成為用戶(hù)在現(xiàn)實(shí)世界活動(dòng)的鏡像。用戶(hù)通過(guò)相互通信形成了一種復(fù)雜的社會(huì)網(wǎng)絡(luò)，該網(wǎng)絡(luò)在一定程度上體現(xiàn)了用戶(hù)的交友偏好、用戶(hù)之間的關(guān)系和用戶(hù)的行為模式。基于社交網(wǎng)絡(luò)的用戶(hù)關(guān)系的預(yù)測(cè)方法成為當(dāng)今社交網(wǎng)絡(luò)的一個(gè)熱點(diǎn)，如：Newman通過(guò)用戶(hù)間的相似度證明了用戶(hù)共同好友的個(gè)數(shù)與他們?cè)趯?lái)會(huì)成為好友的可能性存在正相關(guān)的關(guān)系[1]；Adamic和Adar通過(guò)統(tǒng)計(jì)共同好友的情況來(lái)分析用戶(hù)關(guān)系，采用Adamic-Adar系數(shù)來(lái)衡量用戶(hù)之間社交關(guān)系[2]；Lu考慮到用戶(hù)關(guān)系的差異性，提出一種結(jié)合用戶(hù)關(guān)系權(quán)重的用戶(hù)關(guān)系分析方法[3]。然而上述方法僅僅使用社交網(wǎng)絡(luò)或者地理位置從單一的角度來(lái)挖掘用戶(hù)之間的關(guān)系，沒(méi)有綜合現(xiàn)實(shí)世界和虛擬世界兩方面的特性來(lái)考慮問(wèn)題，從而導(dǎo)致挖掘出來(lái)的用戶(hù)關(guān)系精確度不高。因此，本文考慮現(xiàn)實(shí)世界的用戶(hù)在地理和時(shí)間的重合度基礎(chǔ)上，引入社交網(wǎng)絡(luò)和地理位置相似度進(jìn)行用戶(hù)社交關(guān)系的計(jì)算，以提高用戶(hù)關(guān)系預(yù)測(cè)的精度。

2 用戶(hù)關(guān)系的研究

2.1 問(wèn)題定義

用戶(hù)關(guān)系是用戶(hù)行為動(dòng)力學(xué)的一個(gè)關(guān)鍵性問(wèn)題，它實(shí)質(zhì)上是通過(guò)描述用戶(hù)之間的緊密程度來(lái)確定用戶(hù)的人際關(guān)系，包括血緣、地緣、業(yè)緣等關(guān)系，因此在用戶(hù)關(guān)系的定義中包括家庭關(guān)系、朋友關(guān)系、同事關(guān)系等。本文將主要關(guān)注用戶(hù)關(guān)系中的朋友關(guān)系，結(jié)合社交網(wǎng)絡(luò)和地理位置特征的最佳權(quán)重賦值，提出基于社交網(wǎng)絡(luò)和地理位置相似性的預(yù)測(cè)用戶(hù)關(guān)系預(yù)測(cè)模型。

2.2 用戶(hù)關(guān)系預(yù)測(cè)方法

（1）共同鄰居

以共同鄰居來(lái)衡量用戶(hù)的關(guān)系起源于社交網(wǎng)絡(luò)的鏈接預(yù)測(cè)。鏈接預(yù)測(cè)最常見(jiàn)的方法就是基于節(jié)點(diǎn)相似度的算法[4]。在無(wú)向網(wǎng)絡(luò)中，設(shè)任意節(jié)點(diǎn)u和v，節(jié)點(diǎn)u的鄰居集合為F（u），節(jié)點(diǎn)v的鄰居集合為F（v），則u、v的共同鄰居為F（u）和F（v）的交集，記為F（u）∩F（v）。

Adamic和Adar在考慮社交關(guān)系的基礎(chǔ)上，對(duì)上述公式進(jìn)行改進(jìn)并提出A-A系數(shù)，他們認(rèn)為在鏈接預(yù)測(cè)中，一個(gè)興趣被越少的人擁有，則擁有此興趣的人越可能成為朋友，而大眾興趣的人之間成為朋友的可能性要低一些，因此該系數(shù)給度數(shù)較少的節(jié)點(diǎn)分配較高的相似度值[4]。

（2）地理位置和時(shí)間的重合度

與基于社會(huì)網(wǎng)絡(luò)研究社交關(guān)系類(lèi)似，可基于地理位置相似度來(lái)研究空間位置的相似性，以描述用戶(hù)關(guān)系的緊密程度。一般來(lái)說(shuō)，在地理軌跡上相似程度高的用戶(hù)成為好友的可能性也非常高[5]。

設(shè)用戶(hù)u的軌跡可以用時(shí)間戳和基站ID的組合來(lái)表示，如：， ， …， 。其中，n表示發(fā)生語(yǔ)音業(yè)務(wù)或者數(shù)據(jù)業(yè)務(wù)的次數(shù)；t表示時(shí)間戳；l表示基站的ID。

其中，r的集合為基站Loc。當(dāng)r=li（u）時(shí)，δ（r， li（u））=1，否則為0。

結(jié)合時(shí)間因素，以△T為時(shí)間精度（一般設(shè)為1個(gè)小時(shí)），反映所有用戶(hù)在鄰近時(shí)間相同地理位置的比例。同時(shí)，考慮工作時(shí)間與非工作時(shí)間的影響因素，在工作時(shí)間段和非工作時(shí)間段設(shè)置不同的權(quán)重θ。

（3）地理位置的相似度

地理位置的相似度實(shí)質(zhì)上是通過(guò)對(duì)用戶(hù)的“時(shí)空切片”求余弦相似性即可得到用戶(hù)在地理上移動(dòng)的相關(guān)程度[6]。

（4）基于用戶(hù)社交網(wǎng)絡(luò)和地理位置用戶(hù)關(guān)系預(yù)測(cè)模型

設(shè)用戶(hù)u的社交關(guān)系網(wǎng)絡(luò)是無(wú)向圖，用戶(hù)之間的緊密程度用A-A系數(shù)來(lái)度量，范圍為0～1[6]。按照小時(shí)顆粒度劃分，用戶(hù)在時(shí)間t出現(xiàn)在某個(gè)基站的情況.

每個(gè)用戶(hù)的地理位置關(guān)系用到達(dá)基站的概率表示，通過(guò)對(duì)用戶(hù)的“時(shí)空切片”求余弦相似性即可得到用戶(hù)在地理上移動(dòng)的相似度。

3 基于社交網(wǎng)絡(luò)和地理位置的用戶(hù)關(guān)系

預(yù)測(cè)的應(yīng)用

3.1 數(shù)據(jù)提取

移動(dòng)用戶(hù)在移動(dòng)的過(guò)程中，會(huì)發(fā)生各種手機(jī)業(yè)務(wù)或者進(jìn)行小區(qū)的切換，這些信息都會(huì)記錄在用戶(hù)的軌跡數(shù)據(jù)里。

本文對(duì)某地市運(yùn)營(yíng)商的10萬(wàn)移動(dòng)用戶(hù)在一個(gè)月的全部工作日（工作時(shí)間段08：00：00～17：00：00和非工作時(shí)間段19：00：00～24：00：00）的軌跡數(shù)據(jù)進(jìn)行提取。

3.2 數(shù)據(jù)去噪

本文將結(jié)合地理位置和時(shí)間的重合度進(jìn)行數(shù)據(jù)去噪，考慮到重點(diǎn)是識(shí)別朋友關(guān)系，因此設(shè)置非工作時(shí)間段的權(quán)重θ較大，而在工作時(shí)間段的權(quán)重θ較小。

在本實(shí)驗(yàn)中，設(shè)置非工作時(shí)間段的權(quán)重θ為0.7，而工作時(shí)間段的權(quán)重θ為0.3，以此來(lái)剔除在工作時(shí)間段與用戶(hù)緊密關(guān)系的同事關(guān)系，最后得到滿(mǎn)足一定的CoL閾值的用戶(hù)僅有17 302個(gè)。

3.3 預(yù)測(cè)模型建立

把上述去噪的數(shù)據(jù)按照日期分為兩部分，前20天作為訓(xùn)練集，后10天作為測(cè)試集。參考文獻(xiàn)[6]，設(shè)置γ=0.2。然后根據(jù)用戶(hù)的預(yù)測(cè)關(guān)系模型對(duì)訓(xùn)練集進(jìn)行打分，得到一系列用戶(hù)間的MR值和A-A值。再分別將MR值和A-A值按照大小排序，選擇MR值大于0.25和A-A值大于0.5的作為用戶(hù)關(guān)系的候選集。最后與測(cè)試集進(jìn)行對(duì)比，得到的準(zhǔn)確率。

由圖1可知，僅考慮社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法在預(yù)測(cè)好友關(guān)系的準(zhǔn)確率方面要比MR方法低，因此結(jié)合地理重合度的用戶(hù)關(guān)系預(yù)測(cè)能夠在一定程度上提升用戶(hù)關(guān)系預(yù)測(cè)的準(zhǔn)確度。

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

本文基于真實(shí)的用戶(hù)移動(dòng)軌跡數(shù)據(jù)和用戶(hù)社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，提出了用戶(hù)關(guān)系預(yù)測(cè)的模型，首先基于地理和時(shí)間的重合度算法對(duì)數(shù)據(jù)進(jìn)行去噪，然后再結(jié)合社交網(wǎng)絡(luò)和地理位置的算法預(yù)測(cè)用戶(hù)關(guān)系，該方法能夠較好地衡量用戶(hù)在社交網(wǎng)絡(luò)和地理位置的相似性，從而預(yù)測(cè)用戶(hù)的朋友關(guān)系。實(shí)驗(yàn)證明，基于社交網(wǎng)絡(luò)的相似性和地理位置的算法與基于社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的算法相比具有較高的準(zhǔn)確率。

參考文獻(xiàn)：

[1] Newman M E J. Clustering and preferential attachment in growing networks[J]. Physical Review Letters E， 2001，64（2）： 1-4.

[2] Adamic L A， Adar E. Friends and neighbors on the Web[J]. Social Networks， 2003，25（3）： 211-230.

[3] Liu Z， Zhang Q-M， Lu L， et al. Link prediction in complex networks： a local nave bayes model[J]. Europhysics Letters Association EPL （Europhysics Letters）， 2011，96（4）： 48005-48007.

[4] 張玉梅. 基于動(dòng)態(tài)權(quán)重社交屬性網(wǎng)的鏈接預(yù)測(cè)[D]. 哈爾濱： 哈爾濱工業(yè)大學(xué)， 2015.

[5] Rivera M T， Soderstrom S B， Uzzi B. Dynamics of Dyads in Social Networks： Assortative， Relational， and Proximity Mechanisms[J]. Annual Review of Sociology， 2010，36（1）： 91-115.

[6] 向峰. 基于移動(dòng)網(wǎng)絡(luò)數(shù)據(jù)的用戶(hù)行為與城市感知研究[D]. 武漢： 華中科技大學(xué)， 2014.

[7] 賈若然，劉曙光，孫啟龍. 基于位置軌跡數(shù)據(jù)的用戶(hù)相似性分析[J]. 計(jì)算機(jī)與數(shù)字工程， 2016，44（8）： 1523-1527.

[8] 李德民. 社會(huì)網(wǎng)絡(luò)用戶(hù)關(guān)系分析與預(yù)測(cè)[D]. 濟(jì)南： 山東大學(xué)， 2015.

[9] 孫建偉，李媛，于波. 社交網(wǎng)絡(luò)中用戶(hù)關(guān)系和地理位置組合服務(wù)算法的研究[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2016，37（2）： 298-301.

[10] 劉穎，張煥. 基于社會(huì)網(wǎng)絡(luò)理論的微信用戶(hù)關(guān)系實(shí)證分析[J]. 情報(bào)資料工作， 2014，35（4）： 56-61.