基于位置的社交网络研究综述

朱立超　李治军　姜守旭

摘要：当今，对线上社交网络的研究和线下人们在物理世界中活动的研究都已经很成熟，将线上社交网络和线下物理世界结合起来的异构网络成为研究热点，基于位置的社交网络是通过位置信息理解用户行为和偏好的新型异构网络。 本文从服务和应用的角度对基于位置的社交网络的研究情况进行分析总结，为未来对异构网络进行深入研究以及在基于位置的社交网络中提出新的应用奠定基础。 最后，本文对基于位置的社交网络的研究情况进行总结与展望。

关键词：基于位置的社交网络； 位置信息； 推荐

中图分类号：TP391 文献标识码：A文章编号：2095-2163（2014）04-0060-04

Abstract：Today， online social network and users activity in offline physical world have been studied very well. Heterogeneous network which combines online social network and offline physical world becomes a hot research. Location Based Social Network is a new heterogeneous network which can understand users behavior and preference through location information. This paper analyzes and summarizes the relevant research about LBSN from the aspect of service and application， providing theoretical basis for future research of heterogeneous network and putting forward new applications in LBSN. Furthermore， the paper presents the future research on location based social network.

Key words：Location Based Social Network；Location Information； Recommendation

0引言

由社交网络的众多研究成果可知，基于位置的社交网络（Location Based Social Network，简称LBSN）的正式定义可做如下表述[1]：在现存的社交网络中加入位置因素，以便社会结构中的人们可以共享嵌入位置的信息，而且其中还包含一种新的社会结构，这种新的结构基于人们在物理世界中由位置信息推出的相关性。物理位置分为特定时间下的即时位置和累计一个时间段的历史位置两种情况。用户之间的相关性既包括两个人同时出现在相同的物理位置或者共享类似的历史位置，也包括从位置历史或地理标记的数据得出的共同兴趣、行为或活动。

LBSN的研究原理为[1]：用户和位置是LBSN密切相关的两个主题。用户访问物理世界中的某些位置，留下相应的位置历史并产生位置标记的媒体内容，如果将这些位置按照时间关系连接起来，就会得到每个用户的轨迹。基于这些轨迹，能够建立三个图：位置—位置图、用户—位置图和用户—用户图，如图1所示，这三幅图是LBSN研究的主要依据。

在位置—位置图中，节点表示位置，有向边描述用户在一次旅行中连续访问这些位置，边的权值表示位置之间的相关性。在用户—位置图中，有用户和位置两种节点，用户到位置的边描述用户访问过这个位置，权值表示访问的次数。在用户—用户图中，节点表示用户，边可以表示两层含义，一层是现存社交网络中的原始链接，如好友关系，另一层是从人们的位置信息中推出的新的相似性，也就是用户在物理世界中对同一位置或类似位置的访问次数超过一定数量，可通过推荐机制而将其转换成前一种。

LBSN通过在社交网络中加入位置维度，将社交网络带回现实，缩小了物理世界和在线社交网络的差距，改善了社交网络的服务效果。本文针对基于位置的社交网络的研究现状进行了全面分析和总结。

1基于LBSN的服务

目前出现了各种各样的基于位置的社交网络，在这些网络中，位置是用户情景中的重要元素。根据网络中不同形式的位置信息，大体上可以将基于LBSN的服务分成三类[1]。

1.1由媒体内容表示位置信息

该类网络的典型代表就是Flickr，现在通过对其的阐释剖析来展现这一类网络的性质特点。Flickr中，用户向网络服务上传其私人图片，这些图片是带有地理位置标记的，通过将照片贴上标签或说明，来给其它用户做参考。用户还可以将朋友或家人添加为联系人，也可以建立或加入一个组群来进行经验交流。

从这类网络中直接提取到的位置信息是基于地理标记的媒体内容，用户将在物理世界中产生的、带有地理标记的内容添加到网络中，如文字、照片或视频，而且用户也可以浏览、评价这些内容。通过从这些媒体内容提取到的位置信息和时间信息，可以扩展人们的社会结构，如添加好友。但这类网络服务的焦点仍然是媒体内容，位置只是组织和丰富媒体内容的一个特征，用户间的主要相关性仍然是基于媒体内容本身的。

该类网络即以Foursquare为例。在Foursquare中，主要针对手机用户，通过“签到”来记录用户的所在位置，如百货公司、餐厅、博物馆，并通过积分、勋章等荣誉激励机制鼓励用户“签到”，在网站上共享用户当前的位置及评价，以便在物理世界中的人们能够参考这些评价，以及组织集体活动。

从这类网络中直接提取到的位置信息是基于位置点的信息，用户通过在特定地点进行“签到”来分享其当前位置，如餐馆或博物馆，有了这些即时位置，用户就能从社交网络中发现处于附近范围内的朋友，从而进行一些社会活动。用户也可以通过对这些位置进行评论来给其它用户提供建议。从这类网络中提取出的用户“签到”的位置信息和时间信息是决定用户相关性的主要元素。

1.3由轨迹表示位置信息

GeoLife作为该类网络的代表，主要是由手机或位置获取设备，通过经纬度和时间表示的轨迹形式，记录用户户外活动行程的详细信息，这些活动既包括用户的日常生活如工作、回家，也包括娱乐活动和体育活动，如购物、参观、远足、骑车等。

从这类网络中直接提取到的位置信息是基于轨迹的信息，既关注位置点，又关注连接这些位置点的详细路径，如由经纬度坐标和时间组成的GPS轨迹。这些轨迹不仅描述了用户活动的详细信息，如距离、持续时间、速度，还通过有关轨迹的标签、照片等信息体现了用户经验。此类网络中用户的相关性是由轨迹本身体现的。

2LBSN中的应用

随着LBSN越来越流行，其上开发的应用也日益增多。由于用户和位置是LBSN中的主要元素，本文即从用户和位置的角度对这些应用展开分析总结。

2.1基于用户的应用

从面向用户的角度，基于用户相似性、用户隐私和用户行为等方面，LBSN上的应用主要包括以下五类：

（1）好友推荐。衡量用户之间的相似性，并根据相似性高的用户也可能会有共同兴趣和爱好的推断，即可给特定用户推荐与其相似性高的用户作为好友[2]。通过对地理空间的位置轨迹进行处理，建立一个能够统一描述用户行为的层次结构，每个用户对应这一结构都有自己的层次图，并根据不同用户的层次图来计算彼此之间的相似性[3-4]。也可将地理空间的轨迹表示成语义空间的种类轨迹，在语义轨迹的基础上建立统一描述用户行为的层次结构，每个用户都有自己的层次图，再根据层次图来计算用户相似性。

（2）专家发现。用户对不同的地方有不同的了解，专家则是对一个区域非常了解的用户，其经验和意见对其它用户也将具有极大的参考价值[5-6]。在将用户位置信息表示成统一结构的基础上，可根据HITS（Hypertext Induced Topic Search）模型，将用户对应成hub节点，而将位置对应成authority节点，由此而计算用户的经验值和位置的流行度， 并将用户经验值较高的用户定义为专家进行推荐。

（3）群体挖掘。将所有用户分为不同的团体，可以方便活动相似、兴趣相投的用户进行群体活动[2，7]。通过计算用户在地理空间的相似性将用户分成不同群体，如在一个单位工作的人、在同一小区居住的人[2]。而将用户轨迹描述在语义空间，如电影院、博物馆，也可通过计算用户在语义空间的相似性，将用户分成不同群体，如参加同一社团的人[8]。提出选择与特定地点距离较近并且关系密切的用户群体的问题，将该问题形式化并证明该问题是NP—难的，同时也提出了解决该问题的有效算法，并进一步通过剪枝技术、建立新的索引结构来提高效率。

（4）隐私保护。LBSN中提供的用户移动信息和用户个人信息创造了巨大的商业潜力，但这些商业潜力由于用户对个人隐私的关心可能会被掩盖[9]。根据效益分析，在商业公司要求用户提供个人信息时，评估这些信息可能带来的结果，从而让用户根据结果做出相应的决定，此次研究还对推式和拉式的LBSN服务进行了相应的分析。

（5）行为分析。根据用户的活动通常具有一定的规律性[10]，提出了生活模式的概念，描述用户通常的生活方式和活动规律。研究中使用生活模式标准范式来描述哪类生活规律能够被发现，并提出一个能够有效地从原始数据中挖掘出这些生活模式的工作框架，实验结果表明用户的活动确实存在一定的规律。

2.2基于位置的应用

从面向位置的角度，基于用户相似性、位置间的相关性、位置的种类等方面，LBSN上的应用包括：

（1）路径发现。由于位置获取设备能量消耗、定位误差等原因，轨迹中两个连续采样点之间的路径是不可知的，产生的即是具有不确定性的轨迹[11-12]。可从大量不确定性的轨迹中挖掘两个位置间最可能的路径。文中遵循不确定性加不确定性产生确定性的范式，首先建立路由图，在用户指定的查询下选择出最好的几个路径返回给用户。

（2）商店位置选择。为一个新的商店选择最好的位置是一个很有意义的问题[13]。与传统的方法不同，基于LBSN中收集到的描述用户移动的细粒度数据和位置的流行性，给出问题的形式化定义，并从不同特性的角度进行商店位置预测，如密度特性、竞争特性、区域的流行性等。

（3）区域功能发现。随着城市的发展，城市中形成了不同功能的区域，如教学区、商业区，识别不同区域的功能对城市规划和商业位置选择有很大帮助[14]。提出了解决该问题的方法：将城市根据主干道路分割成不同区域，利用区域中人的移动特性和区域中所包含的兴趣点信息，借助基于主题的模型推导每个区域的功能。

（4）流行位置和流行路径推荐。当用户到一个不熟悉的城市旅行时，推荐这个城市中最为流行、最受欢迎的位置或路径可以给用户带来很大方便[5]。根据HITS模型，在给定区域下，计算位置的流行度，将流行度高的位置作为流行位置推荐给用户；将位置流行度平均到每个与之相连的路径上，再根据路径被用户访问的数量以及这些用户自身的经验值，计算路径的流行度，将流行度较高的路径作为流行路径推荐给用户[6]。也是根据HITS模型，但不是在一个区域中选择流行位置，而是将位置分为不同种类，在同一种类中计算位置流行度，推荐这个种类中流行度最高的位置，如在电影院这个种类下，推荐一个流行度最高的电影院。

（5）行程规划。行程规划是在用户指定起始位置、目的位置及时间间隔的条件下，推荐满足这些约束的、包含兴趣点的路径[15-16]。规划中，根据用户要求挑选出所有从指定位置出发、到达目的位置、满足时间要求并包含有趣位置的路径，再根据路径中包含的有趣位置的个数、在位置间移动需要的时间、完成整条路径的时间以及路径本身的流行度选择得到最好的路径，并为用户做出推荐。

（6）个性化位置推荐。流行位置推荐虽然可以给用户推荐相应的位置，但这些位置并没有考虑用户的个性化信息，即对所有用户推荐的都是相同的位置[17]。通过找到与自己相似性高的用户，再根据这些用户访问的位置进行推荐[18]。也可以通过得到位置间的相关性，再根据与用户经常访问的位置相关性大的位置进行推荐[6]。具体实现是：基于HITS模型得到每个种类下经验值较高的专家，并在用户指定种类下，根据这些种类的专家访问过的位置为用户完成推荐。

（7）位置活动推荐。当用户指定一个位置时，可以给用户推荐在这个位置上发生的最流行的活动，当用户指定一种活动时，也可以给用户推荐进行这种活动的最流行的位置[19]。可通过矩阵来描述每个位置发生的每种活动的情况，但由于在每个位置可以进行的活动是有限的，而活动的种类却是非常多的，因此这个矩阵是非常稀疏的，而进行推荐的主要依据就是矩阵中每个元素的数值。该文使用基于协同过滤的协同矩阵分解方法，利用表示位置与种类关系的矩阵以及表示活动与活动关系的矩阵，填补位置—活动矩阵中的缺失项，由此而完成推荐。

3结束语

由上面的分析可以看出，随着基于位置的社交网络越来越流行，出现了多种多样的基于位置的服务，本文根据这些网络中不同形式的位置信息，将所有网络进行了分类，并给出了每种类型的代表，也进行了相关分析。 随着对基于位置的社交网络的深入研究，产生了许多相关的应用。本文基于用户和位置两大主题，对这些应用进行分类，并详细分析了每种应用的使用场景及实现原理。

通过分析发现，目前虽然有一些关于路径推荐的应用，但推荐的路径是面向所有用户的，并没有考虑用户的个性化信息，本文还没有发现基于位置的社交网络中关于个性化路径的推荐，如用户具有商场—餐馆—电影院的活动习惯，如何挖掘出这个习惯并给用户推荐符合这个习惯的路径，这将是LBSN中又一崭新应用。

参考文献：

[1]Yu Zheng.Location-based social networks： Users [M]. Springer press， 2011.

[2]LI Q， ZHENG Y， XIE X， et al. Mining user similarity based on location history [C]//Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems， GIS 08， ACM， New York， NY， USA， 2008， 34：1–34，10.

[3]XIAO X， ZHENG Y， LUO Q， et al. Finding similar users using category-based location history [C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems， GIS 10， ACM， New York， NY， USA， 2010：442–445.

[4]XIAO X， ZHENG Y， LUO Q， et al. Inferring social ties between users with human location history [J]. Journal of Ambient Intelligence and Humanized Computing， 2012.

[5]ZHENG Y， ZHANG L， XIE X， et al. Mining interesting locations and travel sequences from gps trajectories [C]//Proceedings of the 18th International Conference on World wide web， WWW 09， ACM， New York， NY， USA， 2009， 791–800.

[6]BAO J， ZHENG Y， MOKBEL M .Location-based and preference-aware recommendation using sparse geo-social networking data [C]//20th ACM SIGSPATIAL International Conference on Advances in GIS. Redondo Beach， California ， 2012.

[7]HUNG C C， CHANG C W， PENG W C. Mining trajectory profiles for discovering user communities [C]//Proceedings of the 2009 International Workshop on Location Based Social Networks， LBSN 09， ACM， New York， NY， USA， 2009：1–8.

[8]YANG D N， SHEN C Y， LEE W C， et al. On socio-spatial group query for location-based social networks [C]//SIGKDD， 2012.

[9]XU H， GUPTA S， SHI S. Balancing user privacy concerns in the adoption of location-based services： an empirical analysis across pull-based and push-based applications [C]//iConference， 2009.

[10]YE Y， ZHENG Y， CHEN Y， et al. Mining individual life pattern based on location history [C]//Proceedings of the 2009 Tenth International Conference on Mobile Data Management： Systems， Services and Middleware， MDM09， IEEE Computer Society， Washington， DC， USA， 2009：1–10.

[11]LIU H， WEI L Y， ZHENG Y， et al. Route discovery from mining uncertain trajectories [C]//ICDM， 2011.

[12]WEI L Y， ZHENG Y， PENG W C. Constructing popular routes from uncertain trajectories[C]// KDD， 2012.（下转第67页）

[13]KARAMSHUK D， NOULAS A， SCELLATO S， et al. Geo-spotting： mining online location-based services for optimal retail store placement [C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， KDD 13， ACM， New York， NY， USA， 2013：793–801.

[14]YUAN J， ZHENG Y， XING X. Discovering regions of different functions in a city using human mobility and pois [C]//KDD， 2012.

[15]YOON H， ZHENG Y， XIE X， et al.Smart itinerary based on user-generated gps trajectories [C]// Proceedings of the 7th International Conference on Ubiquitous Intelligence and Computing， UIC10， Springer-Verlag， Berlin， Heidelberg， 2010：19–34.

[16]YOON H， ZHENG Y， XIE X， et al. Social itinerary recommendation from user-generated digital trails [J]. Personal and Ubiquitous Computing ， 2011.

[17]ZHENG Y， ZHANG L， MA Z， et al. Recommending friends and locations based on individual location history [J]. ACM Trans. Web5， 2011， 5：1–5：44.

[18]ZHENG Y， XIE X.Learning travel recommendations from user-generated gps traces [J]. ACM Trans. Intell. Syst. Technol.2， 2011， 2：1–2：29.

[19]ZHENG V W， ZHENG Y， XIE X， et al. Collaborative location and activity recommendations with gps history data[C]//Proceedings of the 19th International Conference on World wide web， WWW 10， ACM， New York， NY， USA， 2010：1029–1038.