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

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

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

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

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

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

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

2.1 問(wèn)題定義

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

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

（1）共同鄰居

以共同鄰居來(lái)衡量用戶的關(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)研究空間位置的相似性，以描述用戶關(guān)系的緊密程度。一般來(lái)說(shuō)，在地理軌跡上相似程度高的用戶成為好友的可能性也非常高[5]。

設(shè)用戶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í)），反映所有用戶在鄰近時(shí)間相同地理位置的比例。同時(shí)，考慮工作時(shí)間與非工作時(shí)間的影響因素，在工作時(shí)間段和非工作時(shí)間段設(shè)置不同的權(quán)重θ。

（3）地理位置的相似度

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

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

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

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

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

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

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

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

本文對(duì)某地市運(yùn)營(yíng)商的10萬(wàn)移動(dòng)用戶在一個(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í)間段與用戶緊密關(guān)系的同事關(guān)系，最后得到滿足一定的CoL閾值的用戶僅有17 302個(gè)。

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

把上述去噪的數(shù)據(jù)按照日期分為兩部分，前20天作為訓(xùn)練集，后10天作為測(cè)試集。參考文獻(xiàn)[6]，設(shè)置γ=0.2。然后根據(jù)用戶的預(yù)測(cè)關(guān)系模型對(duì)訓(xùn)練集進(jìn)行打分，得到一系列用戶間的MR值和A-A值。再分別將MR值和A-A值按照大小排序，選擇MR值大于0.25和A-A值大于0.5的作為用戶關(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é)合地理重合度的用戶關(guān)系預(yù)測(cè)能夠在一定程度上提升用戶關(guān)系預(yù)測(cè)的準(zhǔn)確度。

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

本文基于真實(shí)的用戶移動(dòng)軌跡數(shù)據(jù)和用戶社交網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，提出了用戶關(guān)系預(yù)測(cè)的模型，首先基于地理和時(shí)間的重合度算法對(duì)數(shù)據(jù)進(jìn)行去噪，然后再結(jié)合社交網(wǎng)絡(luò)和地理位置的算法預(yù)測(cè)用戶關(guān)系，該方法能夠較好地衡量用戶在社交網(wǎng)絡(luò)和地理位置的相似性，從而預(yù)測(cè)用戶的朋友關(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ù)的用戶行為與城市感知研究[D]. 武漢： 華中科技大學(xué)， 2014.

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

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

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

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