面向移动社会网络的好友推荐方法

王珊珊　冷甦鹏

摘要：

针对移动社会网络（MSN）的好友推荐问题，提出了一种基于多維相似度的好友推荐方法。该方法隶属于基于内容的好友推荐，但与现有方法相比，不再局限于单一维度的匹配信息，而是从空间、时间和兴趣三个维度出发，判断用户在各个维度上的相似度，最终通过“差异距离”进行综合评判，向目标用户推荐与之在地理位置、在线时间和兴趣爱好上更具一致性的其他用户成为其好友。由实验结果表明，该方法应用于移动社会网络中的好友推荐服务时，其推荐结果查准率接近80%，查准效率接近60%，性能远高于只基于单一维度的好友推荐方法；同时，通过对三维权重值的调整，该方法可应用于多种特性的移动社会网络中。

关键词：

移动社会网络；个性化服务；好友推荐；多维度；相似度

中图分类号：

TP393.07

文献标志码：A

Abstract：

In view of the friend recommendation in Mobile Social Network （MSN）， a new method based on multidimensional similarity was proposed. The method is a kind of method based on content， but not confined to single dimension matching information， it judges users similarity of various dimensions from three aspects of space， time and interest， then gets a comprehensive judgment by “difference distance”. The proposed method can recommend other users to target audience when they are consistent in geographical position， onlinetime and interest. The experimental results show that when the method is used in the friend recommendation of mobile social networks， its precision and efficiency are up to 80% and 60% respectively， the performance is much better than the other friend recommendation methods based on single dimension； at the same time， by adjusting the value of three dimensional weights， the method can be used in a variety of mobile social networks with different characteristics.

英文关键词Key words：

Mobile Social Network （MSN）； personalized service； friend recommendation； multidimensional； precisionsimilarity

0引言

随着无线通信技术和智能终端设备的大力发展，一种新型的社交网络形态，即移动社会网络（Mobile Social Network， MSN）已经兴起。根据消息投递形式的不同，移动社会网络可细分为两个分支，一是由传统在线社会网络（Online Social Network）发展而来的移动社会网络[1]，其消息投递形式延用在线社会网络的服务器转发模式，但在终端设备上进行了革新，由传统的PC端变成了移动智能终端，手机QQ、微信、FourSquare等为广大互联网用户所熟知的网络社交平台都属于该范畴；二是由多个具有相同兴趣爱好或其他共同特点的用户通过移动终端设备互联形成的移动社会网络[2]，其消息投递形式一般采用存储转发模式，该种形式的移动社会网络可摆脱Internet的限制，用户可通过自身的移动性和智能终端设备的存储性达到消息传递的目的。移动社会网络兼有社交网络的社会性和移动网络的移动性，它创造了一种新的社交方式，使虚拟社交和现实社交更为接近，为虚拟世界和现实世界构筑了一座交互的桥梁。

好友关系作为社交网络中人际关系的基本组成，其相关服务和应用一直备受世人瞩目，其中，好友推荐服务已经成为各类社交网络的个性化服务之一。目前，好友推荐方法根据基本性质可分为两类：一是基于内容的好友推荐方法[3]，该方法首先对用户的个人信息进行总汇并对信息进行有效过滤，然后根据用户的特征和目标要求预测并搜索与之匹配程度较高的其他用户推荐成为其好友；二是基于协同过滤的好友推荐方法[4]，该方法一般采用最近邻技术，利用目标用户的最近邻用户对其他用户的评价来预测目标用户对相应用户的喜好程度，从而进行好友推荐。本文提出的好友推荐方法隶属于第一种类型。

常见基于内容的好友推荐方法应用于移动社会网络时，存在的主要问题如下：1）移动社会网络用户在进行注册时，一般只需填写极少的个人信息，而用户信息不全将直接影响部分基于身份信息进行好友推荐的方法产出结果的准确性；2）大部分基于内容的好友推荐方法只使用单一维度的用户

特征进行好友推荐（例如只基于用户身份信息/用户地理位置信息/用户兴趣等），其推荐结果存在一定的局限性。

为解决上述问题，本文提出一种更加适用于移动社会网络特性的基于内容的好友推荐方法，该方法通过分析用户的行为日志，获取用户在时间、空间、兴趣三个维度上的相关数据，并判断用户在各个维度上的相似程度，随后通过文中提出的一种综合指标——“差异距离”，向目标用户推荐与之在地理位置、在线时间和兴趣爱好上更具一致性的其他用户成为其好友。由于该方法参考了多个维度数据，因此在好友推荐的全面性和准确性上有了很大的提高；同时，根据真实的应用场景，在计算“差异距离”时，可对三个维度的权重值进行调整（例如在以位置为主导的社交网络中，可提升“空间相似度”在计算“差异距离”时的权重），因此该推荐方法可适用于更多类型的移动社会网络。

1相关工作

1.1基于移动社会网络的应用

目前基于移動社会网络的应用可以分为两类：一类应用旨在增强原有好友之间的互动联系；另一类旨在为目标用户寻找新朋友。

在增强原有好友间互动联系的应用研究中，文献[5]对纯粹的分布式朋友关系进行了研究；文献[6]在进行功能设计时考虑了支持用户所有联系人相互通信的问题。

在寻找新朋友的应用研究中，文献[7]对基于位置的移动社会网络进行了好友关系关系建模，并利用该模型向目标用户推荐新朋友。

1.2好友推荐方法

根据推荐原理的不同，好友推荐方法可分为两类，一是基于内容的好友推荐方法，二是基于协同过滤的好友推荐方法。

在基于内容的好友推荐中，文献[8]根据用户的年龄、地域、收入等特征，应用关联规则挖掘出目标用户的潜在好友并进行有效推荐；文献[9]通过分析用户的位置列表，基于与位置相关的特征集合，建立了一个好友预测模型；文献[10]则提出了一种社交圈检测算法，通过定义用户间社交圈的相似性，为用户推荐新朋友。这些方法都建立在这样一个假设前提下：如果两个用户关于选定的特征相似，那么这两个用户就应该成为好友关系。

在基于协同过滤的好友推荐中，文献[11]提出基于用户聚类的协同过滤推荐，同时加入用户对曾经使用过的项目的属性，以缩小近邻用户搜索范围；文献[12]利用标签之间的语义关联来衡量对象之间的相似度，从而向目标用户推荐新朋友；文献[13]提出基于移动用户社会化关系挖掘的协同过滤算法，通过对潜在用户的社会化关系进行挖掘，将用户的好友数据加入到传统的协同过滤算法中，提高了用户偏好预测和推荐结果的准确度。基于协同过滤的好友推荐的一个通用前提即为FriendOfFriend原则。

此外，还有一些研究人员通过引入用户在线下的亲密程度，作为线上好友推荐的指标。例如，文献[8]根据用户在现实世界中的会面次数与持续时间来计算用户的亲密度，并据此进行好友推荐。

2面向移动社会网络的好友推荐方法

在本节中，我们将详细阐述面向移动社会网络的好友推荐方法，其中，包括相关指标的定义，兴趣标签的提取与归类和方法的具体实施步骤。

2.1指标定义

移动性是移动社会网络区别于在线社会网络的一大特性，因此将用户的位置信息作为好友推荐的依据内容之一，能有效衡量移动社会网络中两个用户在空间上的相似性。好友间的交互集中体现在实时的信息通信上，因此本文引入在线时间作为好友推荐的参考因素，用于衡量两用户在时间上的相似性。相似的兴趣爱好是促使两个陌生人成为朋友的关键因素，因此本文还使用了用户的兴趣标签衡量两个用户在兴趣上的相似性。

为有效衡量移动社会网络中两个用户在空间、时间和兴趣三个维度上的相似性，本文提出了以下三个指标：

1）离散地理位置相似度：任意用户i和j在空间上的相似性用离散地理位置相似度li， j 表示，具体公式如下：

li， j =∑l∈P， i， j∈Npi，l pj，l‖pi‖×‖pj‖（1）

其中：P表示基站序列集合；N表示用户序列集合；pi，l 表示用户i在位置站点l出现的概率；pi=[pi，1，pi，2，…，pi，m]（m表示位置站点的总数）表示用户i出现在各个基站的概率向量，‖pi‖是pi的范数，本文中优选2范数。

2）在线时间相似度：任意用户i和j在时间上的相似性用在线时间相似度ti， j表示，具体公式如下：

ti， j =∑l∈T， i， j∈Npi，l pj，l‖pi‖×‖pj‖（2）

其中：T表示时间段序列集合，根据具体需要，可将一个自然日划分成若干时段，所有时段组成时间段序列集合；N表示用户序列集合；pi，l 是用户i在时间段l在线的概率；pi=[pi，1，pi，2，…，pi，y]（y表示时间段的总数）表示用户i在各个时间段在线的概率向量， ‖pi‖是pi的范数，本文中优选2范数。pi，l 的具体计算方式为：1/该用户在一个自然日内总在线时间段个数，所有pi，l之和为1。

同一用户每天上、下线时间之间会存在稍许的差异，判别一个用户在某时段是否在线可结合时段划分数目和实际情况确定。

3）兴趣相似度：任意用户i和j在兴趣上的相似性用兴趣相似度hi， j表示，具体公式如下：

hi， j =∑l∈H， i， j∈Npi，l pj，l‖pi‖×‖pj‖（3）

其中：H表示兴趣标签序列集合；N表示用户序列集合；pi，l是用户拥有兴趣l的概率；pi=[pi，1，pi，2，…，pi，y]（k表示兴趣标签的总数）表示用户i拥有的各种兴趣标签的概率向量，‖pi‖是pi的范数，本文中优选2范数。pi，l的具体计算方式为：1/该用户所拥有的总兴趣标签数，所有pi，l之和为1。

为了使三个维度上的相似度达到统一，共同作用于判断移动社会网络中任意两个用户间的相似性，本文提出了一个综合性指标——“差异距离”，具体公式如下：

di， j=2α（li， j-）2+β（ti， j-）2+γ（hi， j-）2（4）

di， j表示用户i和用户j的差异距离，其中，α、β、γ 表示三个相似度的对应权重，取值范围为[0，1]，三者相加等于1，可根据具体使用场景进行权重的调整，默认值为1/3。L 、T 和H 分别表示离散地理位置相似度li， j、在线时间相似度ti， j、兴趣相似性hi， j的均值，具体计算公式为：

=n（n+1）2∑i∈N∑j∈Nli， j（5）

=n（n+1）2∑i∈N∑j∈Nti， j（6）

=n（n+1）2∑i∈N∑j∈Nhi， j（7）

其中：N表示用户序列集合，n表示用户人数。

2.2兴趣标签的提取与归纳

不同于地理位置信息和在线时间信息可以直接从相关日志中直接提取，随着用户生成内容（User Generated Content， UGC）在社交网络中的广泛应用，用户的兴趣标签常常需要从用户自定义文本中提取。为了更加精确地计算用户间的兴趣相似度，本文构建了一个二级兴趣标签分类体系，并根据该分类体系，提出了一种简单的用户兴趣标签提取方法。

由于用户兴趣大类存在共通性，因此本文采用间接的方式，通过统计某在线社交网站上某些类别的公共主页和粉丝数目预估用户的兴趣情况，以此构建二级兴趣标签分类体系。

首先提取公共主页的标签，根据标签出现次数统计，删除出现次数少的标签；然后对结果进行人工筛选，去除无明显意义的标签；最后通过合并同类别标签，得到二级兴趣标签分类体系。结果示例如表1所示。

2.3方法实施步骤

面向移动社会网络的好友推荐算法的具体实施步骤如图2所示如下：

步驟1导入用户的地理位置日志，计算任意两个用户之间的离散地理位置相似度；

步骤2导入用户的在线时间日志，计算任意两个用户之间的在线时间相似度；

步骤3导入用户自定义文本日志，提取并归纳用户兴趣标签，计算任意两个用户之间的兴趣相似度；

步骤4根据离散地理位置相似度、在线时间相似度和兴趣相似度计算任意两个用户之间的差异距离；

步骤5选定目标用户，根据目标用户与其他用户的差异距离，将排名在topN（N的数值可根据具体的应用场景进行确定）范围内的其他用户推荐给目标用户，成为其好友候选人。

3实验结果与分析

3.1实验数据和方法

为有效对本文提出的面向移动社会网络的好友推荐方法

进行验证，实验选取了来自Foursquare这一移动社交网络的真实数据集。该数据集包括2011年2月位于纽约的501940个匿名用户数据和位于洛杉矶的717382个匿名用户数据，具体包含用户的基本信息、签到信息和好友关系信息。

由于数据集中的数据并不独立存在本文提出好友推荐方法中所需的三个参数——地理位置、在线时间、兴趣标签，因此在开始实验验证前，需要对三个参数进行提取。

用户签到信息的格式如图2所示，其中User ID表示用户ID，Tip表示用户每次签到的具体内容，用户每签到一次，就会产生一个Tip数据，主要信息字段包括Venue ID，Text和Create Time，其中：Venue ID表示街道ID，Text是用户对本次签到的文本描述信息，Create Time是用户签到时间。

本文将Venue ID作为地理位置信息，将Create Time作为在线时间信息，并利2.2节中提出的兴趣标签提取和归类方法从Text短文本中提取关键字作为用户的兴趣标签。

为验证推荐方法在具体应用场景中的推荐性能，本文以上述两个城市的实验数据为例，将推荐方法计算产生的待推荐用户与目标用户的真实好友比较，待推荐用户中包含越多目标用户的真实好友，说明推荐方法的效果越好。本文采用R/N和R/A作为推荐方法的优化和评价指标。R/N由查准率（Precision）演变而来，反应推荐结果的查准率，其中（R/N）single表示推荐方法作用于单个用户的查准率，（R/N）average表示推荐方法作用于全部用户的平均查准率。

（R/N）single=R/N（8）

其中：R表示待推荐用户中包含的目标用户真实好友数，N表示目标用户的真实好友总数。

（R/N）average=1M∑Mi=1[（R/N）single]i（9）

其中：M表示用户总数。

R/A反映推荐方法的效率，其中（R/A）single表示推荐方法作用于单个用户的效率，（R/A）average表示推荐方法作用于全部用户的平均效率。

（R/A）single=R/A（10）

其中：R表示待推荐用户中包含的目标用户真实好友数，A表示待推荐好友总数。

（R/A）average=1M∑Mi=1[（R/A）single]i（11）

其中：M表示用户总数。

3.2实验结果

实验首先选取了以下四种情况，将与目标用户差异距离值排名在前百分之一的其他用户作为待推荐用户，它们是：case1（α=1/3， β=1/3，γ=1/3）、case2（α=1， β=0，γ=0 ）、case3（α=0， β=1，γ=0 ）和case4（α=0， β=0，γ=1 ）。其中，case1代表基于多维度信息的好友推荐方法，而case2～4分别代表了只以于地理位置信息、在线时间信息和兴趣信息为导向的基于单一维度信息的好友推荐方法。四种情况应用在纽约和洛杉矶两个城市数据集上的（R/N）average和（R/A）average如表2所示。

α=1/3， β=1/3，γ=1/3时，其推荐结果的平均查准率接近80%，查准效率接近60%，明显优于其他三种情况。产生该结果的主要原因是实验数据来自Foursquare，而Foursquare是一个以位置为主导的移动社交平台，因此相比只依据在线时间或用户兴趣进行好友推荐的情况，只依据用户地理位置进行好友推荐时，其推荐结果要令人满意得多；但是也应该看到，当在地理位置的基础上引入在线时间和用户兴趣后，好友推荐结果的平均查准率和平均查准效率有着将近15%的提升。由此可见，依据多维度数据产生的好友推荐结果明显优于只依据单一维度数据产生的好友推荐结果。

为了进一步验证本文提出的面向移动社会网络的好友推荐方法的有效性，将其与文献[8]提出的基于用户基本信息的好友推荐方法和文献[13]提出的基于移动用户社会化关系挖掘的好友推荐方法进行对比，实验时将三种方法作用于纽约用户的数据集上，具体实验结果如表3所示。

由表3可知，基于三维相似度的好友推荐方法明显优于基于用户基本信息的好友推荐方法和基于社会化关系挖掘的好友推荐方法，其主要原因是Foursqaure用户在进行用户注册时，只需要填写邮箱、性别和所在城市三个基本信息，基本信息的缺乏导致传统的基于用户基本信息进行好友推荐的方法应用于移动社会网络时，出现推荐结果极差的情况；基于社会化关系挖掘的好友推荐方法相比基于用户基本信息进行好友推荐方法在推荐查准率和推荐效率上有很大的提升，但因为该方法只参考用户间的社会关系，而实验数据集上又缺乏对好友亲密度进行进一步确定的数据，因此在推荐结果上还是逊色于基于三维相似度的好友推荐方法。

从实验结果可知，本文提出的好友推荐方法在应用于移动社会网络时，可以取得较好的推荐结果；而且由于三维权重值可根据具体应用场景灵活调整，该方法可以应用于多种特性的移动社会网络。

4结语

本文对移动社会网络下的好友推荐问题进行了研究，结合用户在移动社会网络中所表现的特性和现实生活中人们交友的一般前提，从空间、时间和兴趣爱好三个维度出发，为目标用户推荐与其匹配度较高的其他用户成为其好友。由于该方法在进行相似度计算时，并未考虑在同一地点、同一时间段的重复出现或上线的情况，在接下来的工作中，可将频率引入相似度的计算，进一步提升推荐好友的质量。另外，由于该方法中需要使用用户的兴趣标签数据，而很多社交网络的后台数据中并不直接包含此项，常常需要从用户的自定义信息、行为信息或是关注信息中进行提取，而在本次实验数据处理时，只使用了依据自定义二级兴趣标签分类体系的兴趣标签提取和归类方法，因此在今后的工作中，可引入移动社交网络中用户兴趣挖掘的相关方法，在扩展该推荐方法的应用场景的同时，也进一步提升推荐结果的可靠性和准确性。

参考文献：

[1]

PALLIS G， ZEINALIPOURYAZTI D， DIKAIAKOS M D. Online social networks： status and trends [M]// VAKALI A， JAIN L C. New Directions in Web Data Management 1. Berlin： Springer， 2011： 213-234.

[2]

PAN H， CROWCROFT J， YONEKI E. BUBBLE rap： socialbased forwarding in delaytolerant networks [J]. IEEE Transactions on Mobile Computing， 2011， 10（11）： 1576-1589.

[3]

吴不晓，肖菁.基于用户标注行为的潜在好友推荐[J].计算机应用，2015，35（6）：1663-1667.（WU B X， XIAO J. Potential friend recommendation based on user tagging [J]. Journal of Computer Applications， 2015， 35（6）： 1663-1667.）

[4]

何靜，潘善亮，韩露.基于双边兴趣的社交网好友推荐方法研究[J].计算机工程与应用，2015，51（6）：108-113.（HE J， PAN S L， HAN L. Recommendation algorithm of SNS friends based on bilateral interest[J]. Computer Engineering and Applications， 2015， 51（6）： 108-113.）

[5]

ARB M V， BADER M， KUHN M， et al. VENETA： serverless friendoffriend detection in mobile social networking [C]// WIMOB 08： Proceedings of the 2008 IEEE International Conference on Wireless and Mobile Computing， Networking and Communication. Washington， DC： IEEE Computer Society， 2008： 184-189.

[6]

COUNTS S. Groupbased mobile messaging in support of the social side of leisure [J]. Computer Supported Cooperative Work， 2007， 16（1/2）： 75-97.

[7]

LI N， CHEN G. Multilayered friendship modeling for locationbased mobile social networks [C]// MobiQuitous 09： Proceedings of the 2009 6th Annual International Mobile and Ubiquitous Systems： Networking and Services， MobiQuitous. Piscataway， NJ： IEEE， 2009： 1-10.

[8]

GUO B， YU Z， ZHOU X， et al. Hybrid SN： interlinking opportunistic and online communities to augment information dissemination [C]// UICATC 12： Proceedings of the 2012 9th International Conference on Ubiquitous Intelligence and Computing and 9th International Conference on Autonomic and Trusted Computing. Washington， DC： IEEE Computer Society， 2012： 188-195.

[9]

CRANSHAW J， TOCH E， HONG J， et al. Bridging the gap between physical location and online social networks [C]// UbiComp 10： Proceedings of the 12th ACM International Conference on Ubiquitous Computing. New York： ACM， 2010： 119-128.