杜翠凤+陈少权
【摘 要】为了解决社交网络用户关系预测的不精确问题,通过采用时空分析方法对移动通信用户的轨迹和通话关系数据进行分析,研究了结合地理和时间的重合度以及基于用户时空特征权重赋值算法,并提出了基于社交网络和地理位置相似度的用户关系预测方案。经过实验证明,提出的算法能够改善社交网络预测的精度。
【关键词】社交网络 地理位置 用户关系 相似度
doi:10.3969/j.issn.1006-1010.2017.08.004 中图分类号:TP391.4 文献标志码:A 文章编号:1006-1010(2017)08-0021-03
引用格式:杜翠凤,陈少权. 基于社交网络和地理位置的用户关系预测[J]. 移动通信, 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 引言
随着移动应用的发展,以QQ、微信为代表的基于社交网络和位置融合的移动应用已经成为用户在现实世界活动的镜像。用户通过相互通信形成了一种复杂的社会网络,该网络在一定程度上体现了用户的交友偏好、用户之间的关系和用户的行为模式。基于社交网络的用户关系的预测方法成为当今社交网络的一个热点,如:Newman通过用户间的相似度证明了用户共同好友的个数与他们在将来会成为好友的可能性存在正相关的关系[1];Adamic和Adar通过统计共同好友的情况来分析用户关系,采用Adamic-Adar系数来衡量用户之间社交关系[2];Lu考虑到用户关系的差异性,提出一种结合用户关系权重的用户关系分析方法[3]。然而上述方法仅仅使用社交网络或者地理位置从单一的角度来挖掘用户之间的关系,没有综合现实世界和虚拟世界两方面的特性来考虑问题,从而导致挖掘出来的用户关系精确度不高。因此,本文考虑现实世界的用户在地理和时间的重合度基础上,引入社交网络和地理位置相似度进行用户社交关系的计算,以提高用户关系预测的精度。
2 用户关系的研究
2.1 问题定义
用户关系是用户行为动力学的一个关键性问题,它实质上是通过描述用户之间的紧密程度来确定用户的人际关系,包括血缘、地缘、业缘等关系,因此在用户关系的定义中包括家庭关系、朋友关系、同事关系等。本文将主要关注用户关系中的朋友关系,结合社交网络和地理位置特征的最佳权重赋值,提出基于社交网络和地理位置相似性的预测用户关系预测模型。
2.2 用戶关系预测方法
(1)共同邻居
以共同邻居来衡量用户的关系起源于社交网络的链接预测。链接预测最常见的方法就是基于节点相似度的算法[4]。在无向网络中,设任意节点u和v,节点u的邻居集合为F(u),节点v的邻居集合为F(v),则u、v的共同邻居为F(u)和F(v)的交集,记为F(u)∩F(v)。
Adamic和Adar在考虑社交关系的基础上,对上述公式进行改进并提出A-A系数,他们认为在链接预测中,一个兴趣被越少的人拥有,则拥有此兴趣的人越可能成为朋友,而大众兴趣的人之间成为朋友的可能性要低一些,因此该系数给度数较少的节点分配较高的相似度值[4]。
(2)地理位置和时间的重合度
与基于社会网络研究社交关系类似,可基于地理位置相似度来研究空间位置的相似性,以描述用户关系的紧密程度。一般来说,在地理轨迹上相似程度高的用户成为好友的可能性也非常高[5]。
设用户u的轨迹可以用时间戳和基站ID的组合来表示,如:
其中,r的集合为基站Loc。当r=li(u)时,δ(r, li(u))=1,否则为0。
结合时间因素,以△T为时间精度(一般设为1个小时),反映所有用户在邻近时间相同地理位置的比例。同时,考虑工作时间与非工作时间的影响因素,在工作时间段和非工作时间段设置不同的权重θ。
(3)地理位置的相似度
地理位置的相似度实质上是通过对用户的“时空切片”求余弦相似性即可得到用户在地理上移动的相关程度[6]。
(4)基于用户社交网络和地理位置用户关系预测模型
设用户u的社交关系网络是无向图,用户之间的紧密程度用A-A系数来度量,范围为0~1[6]。按照小时颗粒度划分,用户在时间t出现在某个基站的情况.
每个用户的地理位置关系用到达基站的概率表示,通过对用户的“时空切片”求余弦相似性即可得到用户在地理上移动的相似度。
3 基于社交网络和地理位置的用户关系
预测的应用
3.1 数据提取
移动用户在移动的过程中,会发生各种手机业务或者进行小区的切换,这些信息都会记录在用户的轨迹数据里。
本文对某地市运营商的10万移动用户在一个月的全部工作日(工作时间段08:00:00~17:00:00和非工作时间段19:00:00~24:00:00)的轨迹数据进行提取。
3.2 数据去噪
本文将结合地理位置和时间的重合度进行数据去噪,考虑到重点是识别朋友关系,因此设置非工作时间段的权重θ较大,而在工作时间段的权重θ较小。
在本实验中,设置非工作时间段的权重θ为0.7,而工作时间段的权重θ为0.3,以此来剔除在工作时间段与用户紧密关系的同事关系,最后得到满足一定的CoL阈值的用户仅有17 302个。
3.3 预测模型建立
把上述去噪的数据按照日期分为两部分,前20天作为训练集,后10天作为测试集。参考文献[6],设置γ=0.2。然后根据用户的预测关系模型对训练集进行打分,得到一系列用户间的MR值和A-A值。再分别将MR值和A-A值按照大小排序,选择MR值大于0.25和A-A值大于0.5的作为用户关系的候选集。最后与测试集进行对比,得到的准确率。
由图1可知,仅考虑社交网络拓扑结构的方法在预测好友关系的准确率方面要比MR方法低,因此结合地理重合度的用户关系预测能够在一定程度上提升用户关系预测的准确度。
4 结束语
本文基于真实的用户移动轨迹数据和用户社交网络的拓扑结构,提出了用户关系预测的模型,首先基于地理和时间的重合度算法对数据进行去噪,然后再结合社交网络和地理位置的算法预测用户关系,该方法能够较好地衡量用户在社交网络和地理位置的相似性,从而预测用户的朋友关系。实验证明,基于社交网络的相似性和地理位置的算法与基于社交网络拓扑结构的算法相比具有较高的准确率。
参考文献:
[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]. 哈尔滨: 哈尔滨工业大学, 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]. 武汉: 华中科技大学, 2014.
[7] 贾若然,刘曙光,孙启龙. 基于位置轨迹数据的用户相似性分析[J]. 计算机与数字工程, 2016,44(8): 1523-1527.
[8] 李德民. 社会网络用户关系分析与预测[D]. 济南: 山东大学, 2015.
[9] 孙建伟,李媛,于波. 社交网络中用户关系和地理位置组合服务算法的研究[J]. 小型微型计算机系统, 2016,37(2): 298-301.
[10] 刘颖,张焕. 基于社会网络理论的微信用户关系实证分析[J]. 情报资料工作, 2014,35(4): 56-61.