基于位置的社交網(wǎng)絡(luò)研究綜述

朱立超　李治軍　姜守旭

摘要：當(dāng)今，對線上社交網(wǎng)絡(luò)的研究和線下人們在物理世界中活動的研究都已經(jīng)很成熟，將線上社交網(wǎng)絡(luò)和線下物理世界結(jié)合起來的異構(gòu)網(wǎng)絡(luò)成為研究熱點，基于位置的社交網(wǎng)絡(luò)是通過位置信息理解用戶行為和偏好的新型異構(gòu)網(wǎng)絡(luò)。 本文從服務(wù)和應(yīng)用的角度對基于位置的社交網(wǎng)絡(luò)的研究情況進(jìn)行分析總結(jié)，為未來對異構(gòu)網(wǎng)絡(luò)進(jìn)行深入研究以及在基于位置的社交網(wǎng)絡(luò)中提出新的應(yīng)用奠定基礎(chǔ)。 最后，本文對基于位置的社交網(wǎng)絡(luò)的研究情況進(jìn)行總結(jié)與展望。

關(guān)鍵詞：基于位置的社交網(wǎng)絡(luò)； 位置信息； 推薦

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：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引言

由社交網(wǎng)絡(luò)的眾多研究成果可知，基于位置的社交網(wǎng)絡(luò)（Location Based Social Network，簡稱LBSN）的正式定義可做如下表述[1]：在現(xiàn)存的社交網(wǎng)絡(luò)中加入位置因素，以便社會結(jié)構(gòu)中的人們可以共享嵌入位置的信息，而且其中還包含一種新的社會結(jié)構(gòu)，這種新的結(jié)構(gòu)基于人們在物理世界中由位置信息推出的相關(guān)性。物理位置分為特定時間下的即時位置和累計一個時間段的歷史位置兩種情況。用戶之間的相關(guān)性既包括兩個人同時出現(xiàn)在相同的物理位置或者共享類似的歷史位置，也包括從位置歷史或地理標(biāo)記的數(shù)據(jù)得出的共同興趣、行為或活動。

LBSN的研究原理為[1]：用戶和位置是LBSN密切相關(guān)的兩個主題。用戶訪問物理世界中的某些位置，留下相應(yīng)的位置歷史并產(chǎn)生位置標(biāo)記的媒體內(nèi)容，如果將這些位置按照時間關(guān)系連接起來，就會得到每個用戶的軌跡。基于這些軌跡，能夠建立三個圖：位置—位置圖、用戶—位置圖和用戶—用戶圖，如圖1所示，這三幅圖是LBSN研究的主要依據(jù)。

在位置—位置圖中，節(jié)點表示位置，有向邊描述用戶在一次旅行中連續(xù)訪問這些位置，邊的權(quán)值表示位置之間的相關(guān)性。在用戶—位置圖中，有用戶和位置兩種節(jié)點，用戶到位置的邊描述用戶訪問過這個位置，權(quán)值表示訪問的次數(shù)。在用戶—用戶圖中，節(jié)點表示用戶，邊可以表示兩層含義，一層是現(xiàn)存社交網(wǎng)絡(luò)中的原始鏈接，如好友關(guān)系，另一層是從人們的位置信息中推出的新的相似性，也就是用戶在物理世界中對同一位置或類似位置的訪問次數(shù)超過一定數(shù)量，可通過推薦機(jī)制而將其轉(zhuǎn)換成前一種。

LBSN通過在社交網(wǎng)絡(luò)中加入位置維度，將社交網(wǎng)絡(luò)帶回現(xiàn)實，縮小了物理世界和在線社交網(wǎng)絡(luò)的差距，改善了社交網(wǎng)絡(luò)的服務(wù)效果。本文針對基于位置的社交網(wǎng)絡(luò)的研究現(xiàn)狀進(jìn)行了全面分析和總結(jié)。

1基于LBSN的服務(wù)

目前出現(xiàn)了各種各樣的基于位置的社交網(wǎng)絡(luò)，在這些網(wǎng)絡(luò)中，位置是用戶情景中的重要元素。根據(jù)網(wǎng)絡(luò)中不同形式的位置信息，大體上可以將基于LBSN的服務(wù)分成三類[1]。

1.1由媒體內(nèi)容表示位置信息

該類網(wǎng)絡(luò)的典型代表就是Flickr，現(xiàn)在通過對其的闡釋剖析來展現(xiàn)這一類網(wǎng)絡(luò)的性質(zhì)特點。Flickr中，用戶向網(wǎng)絡(luò)服務(wù)上傳其私人圖片，這些圖片是帶有地理位置標(biāo)記的，通過將照片貼上標(biāo)簽或說明，來給其它用戶做參考。用戶還可以將朋友或家人添加為聯(lián)系人，也可以建立或加入一個組群來進(jìn)行經(jīng)驗交流。

從這類網(wǎng)絡(luò)中直接提取到的位置信息是基于地理標(biāo)記的媒體內(nèi)容，用戶將在物理世界中產(chǎn)生的、帶有地理標(biāo)記的內(nèi)容添加到網(wǎng)絡(luò)中，如文字、照片或視頻，而且用戶也可以瀏覽、評價這些內(nèi)容。通過從這些媒體內(nèi)容提取到的位置信息和時間信息，可以擴(kuò)展人們的社會結(jié)構(gòu)，如添加好友。但這類網(wǎng)絡(luò)服務(wù)的焦點仍然是媒體內(nèi)容，位置只是組織和豐富媒體內(nèi)容的一個特征，用戶間的主要相關(guān)性仍然是基于媒體內(nèi)容本身的。

該類網(wǎng)絡(luò)即以Foursquare為例。在Foursquare中，主要針對手機(jī)用戶，通過“簽到”來記錄用戶的所在位置，如百貨公司、餐廳、博物館，并通過積分、勛章等榮譽(yù)激勵機(jī)制鼓勵用戶“簽到”，在網(wǎng)站上共享用戶當(dāng)前的位置及評價，以便在物理世界中的人們能夠參考這些評價，以及組織集體活動。

從這類網(wǎng)絡(luò)中直接提取到的位置信息是基于位置點的信息，用戶通過在特定地點進(jìn)行“簽到”來分享其當(dāng)前位置，如餐館或博物館，有了這些即時位置，用戶就能從社交網(wǎng)絡(luò)中發(fā)現(xiàn)處于附近范圍內(nèi)的朋友，從而進(jìn)行一些社會活動。用戶也可以通過對這些位置進(jìn)行評論來給其它用戶提供建議。從這類網(wǎng)絡(luò)中提取出的用戶“簽到”的位置信息和時間信息是決定用戶相關(guān)性的主要元素。

1.3由軌跡表示位置信息

GeoLife作為該類網(wǎng)絡(luò)的代表，主要是由手機(jī)或位置獲取設(shè)備，通過經(jīng)緯度和時間表示的軌跡形式，記錄用戶戶外活動行程的詳細(xì)信息，這些活動既包括用戶的日常生活如工作、回家，也包括娛樂活動和體育活動，如購物、參觀、遠(yuǎn)足、騎車等。

從這類網(wǎng)絡(luò)中直接提取到的位置信息是基于軌跡的信息，既關(guān)注位置點，又關(guān)注連接這些位置點的詳細(xì)路徑，如由經(jīng)緯度坐標(biāo)和時間組成的GPS軌跡。這些軌跡不僅描述了用戶活動的詳細(xì)信息，如距離、持續(xù)時間、速度，還通過有關(guān)軌跡的標(biāo)簽、照片等信息體現(xiàn)了用戶經(jīng)驗。此類網(wǎng)絡(luò)中用戶的相關(guān)性是由軌跡本身體現(xiàn)的。

2LBSN中的應(yīng)用

隨著LBSN越來越流行，其上開發(fā)的應(yīng)用也日益增多。由于用戶和位置是LBSN中的主要元素，本文即從用戶和位置的角度對這些應(yīng)用展開分析總結(jié)。

2.1基于用戶的應(yīng)用

從面向用戶的角度，基于用戶相似性、用戶隱私和用戶行為等方面，LBSN上的應(yīng)用主要包括以下五類：

（1）好友推薦。衡量用戶之間的相似性，并根據(jù)相似性高的用戶也可能會有共同興趣和愛好的推斷，即可給特定用戶推薦與其相似性高的用戶作為好友[2]。通過對地理空間的位置軌跡進(jìn)行處理，建立一個能夠統(tǒng)一描述用戶行為的層次結(jié)構(gòu)，每個用戶對應(yīng)這一結(jié)構(gòu)都有自己的層次圖，并根據(jù)不同用戶的層次圖來計算彼此之間的相似性[3-4]。也可將地理空間的軌跡表示成語義空間的種類軌跡，在語義軌跡的基礎(chǔ)上建立統(tǒng)一描述用戶行為的層次結(jié)構(gòu)，每個用戶都有自己的層次圖，再根據(jù)層次圖來計算用戶相似性。

（2）專家發(fā)現(xiàn)。用戶對不同的地方有不同的了解，專家則是對一個區(qū)域非常了解的用戶，其經(jīng)驗和意見對其它用戶也將具有極大的參考價值[5-6]。在將用戶位置信息表示成統(tǒng)一結(jié)構(gòu)的基礎(chǔ)上，可根據(jù)HITS（Hypertext Induced Topic Search）模型，將用戶對應(yīng)成hub節(jié)點，而將位置對應(yīng)成authority節(jié)點，由此而計算用戶的經(jīng)驗值和位置的流行度， 并將用戶經(jīng)驗值較高的用戶定義為專家進(jìn)行推薦。

（3）群體挖掘。將所有用戶分為不同的團(tuán)體，可以方便活動相似、興趣相投的用戶進(jìn)行群體活動[2，7]。通過計算用戶在地理空間的相似性將用戶分成不同群體，如在一個單位工作的人、在同一小區(qū)居住的人[2]。而將用戶軌跡描述在語義空間，如電影院、博物館，也可通過計算用戶在語義空間的相似性，將用戶分成不同群體，如參加同一社團(tuán)的人[8]。提出選擇與特定地點距離較近并且關(guān)系密切的用戶群體的問題，將該問題形式化并證明該問題是NP—難的，同時也提出了解決該問題的有效算法，并進(jìn)一步通過剪枝技術(shù)、建立新的索引結(jié)構(gòu)來提高效率。

（4）隱私保護(hù)。LBSN中提供的用戶移動信息和用戶個人信息創(chuàng)造了巨大的商業(yè)潛力，但這些商業(yè)潛力由于用戶對個人隱私的關(guān)心可能會被掩蓋[9]。根據(jù)效益分析，在商業(yè)公司要求用戶提供個人信息時，評估這些信息可能帶來的結(jié)果，從而讓用戶根據(jù)結(jié)果做出相應(yīng)的決定，此次研究還對推式和拉式的LBSN服務(wù)進(jìn)行了相應(yīng)的分析。

（5）行為分析。根據(jù)用戶的活動通常具有一定的規(guī)律性[10]，提出了生活模式的概念，描述用戶通常的生活方式和活動規(guī)律。研究中使用生活模式標(biāo)準(zhǔn)范式來描述哪類生活規(guī)律能夠被發(fā)現(xiàn)，并提出一個能夠有效地從原始數(shù)據(jù)中挖掘出這些生活模式的工作框架，實驗結(jié)果表明用戶的活動確實存在一定的規(guī)律。

2.2基于位置的應(yīng)用

從面向位置的角度，基于用戶相似性、位置間的相關(guān)性、位置的種類等方面，LBSN上的應(yīng)用包括：

（1）路徑發(fā)現(xiàn)。由于位置獲取設(shè)備能量消耗、定位誤差等原因，軌跡中兩個連續(xù)采樣點之間的路徑是不可知的，產(chǎn)生的即是具有不確定性的軌跡[11-12]?？蓮拇罅坎淮_定性的軌跡中挖掘兩個位置間最可能的路徑。文中遵循不確定性加不確定性產(chǎn)生確定性的范式，首先建立路由圖，在用戶指定的查詢下選擇出最好的幾個路徑返回給用戶。

（2）商店位置選擇。為一個新的商店選擇最好的位置是一個很有意義的問題[13]。與傳統(tǒng)的方法不同，基于LBSN中收集到的描述用戶移動的細(xì)粒度數(shù)據(jù)和位置的流行性，給出問題的形式化定義，并從不同特性的角度進(jìn)行商店位置預(yù)測，如密度特性、競爭特性、區(qū)域的流行性等。

（3）區(qū)域功能發(fā)現(xiàn)。隨著城市的發(fā)展，城市中形成了不同功能的區(qū)域，如教學(xué)區(qū)、商業(yè)區(qū)，識別不同區(qū)域的功能對城市規(guī)劃和商業(yè)位置選擇有很大幫助[14]。提出了解決該問題的方法：將城市根據(jù)主干道路分割成不同區(qū)域，利用區(qū)域中人的移動特性和區(qū)域中所包含的興趣點信息，借助基于主題的模型推導(dǎo)每個區(qū)域的功能。

（4）流行位置和流行路徑推薦。當(dāng)用戶到一個不熟悉的城市旅行時，推薦這個城市中最為流行、最受歡迎的位置或路徑可以給用戶帶來很大方便[5]。根據(jù)HITS模型，在給定區(qū)域下，計算位置的流行度，將流行度高的位置作為流行位置推薦給用戶；將位置流行度平均到每個與之相連的路徑上，再根據(jù)路徑被用戶訪問的數(shù)量以及這些用戶自身的經(jīng)驗值，計算路徑的流行度，將流行度較高的路徑作為流行路徑推薦給用戶[6]。也是根據(jù)HITS模型，但不是在一個區(qū)域中選擇流行位置，而是將位置分為不同種類，在同一種類中計算位置流行度，推薦這個種類中流行度最高的位置，如在電影院這個種類下，推薦一個流行度最高的電影院。

（5）行程規(guī)劃。行程規(guī)劃是在用戶指定起始位置、目的位置及時間間隔的條件下，推薦滿足這些約束的、包含興趣點的路徑[15-16]。規(guī)劃中，根據(jù)用戶要求挑選出所有從指定位置出發(fā)、到達(dá)目的位置、滿足時間要求并包含有趣位置的路徑，再根據(jù)路徑中包含的有趣位置的個數(shù)、在位置間移動需要的時間、完成整條路徑的時間以及路徑本身的流行度選擇得到最好的路徑，并為用戶做出推薦。

（6）個性化位置推薦。流行位置推薦雖然可以給用戶推薦相應(yīng)的位置，但這些位置并沒有考慮用戶的個性化信息，即對所有用戶推薦的都是相同的位置[17]。通過找到與自己相似性高的用戶，再根據(jù)這些用戶訪問的位置進(jìn)行推薦[18]。也可以通過得到位置間的相關(guān)性，再根據(jù)與用戶經(jīng)常訪問的位置相關(guān)性大的位置進(jìn)行推薦[6]。具體實現(xiàn)是：基于HITS模型得到每個種類下經(jīng)驗值較高的專家，并在用戶指定種類下，根據(jù)這些種類的專家訪問過的位置為用戶完成推薦。

（7）位置活動推薦。當(dāng)用戶指定一個位置時，可以給用戶推薦在這個位置上發(fā)生的最流行的活動，當(dāng)用戶指定一種活動時，也可以給用戶推薦進(jìn)行這種活動的最流行的位置[19]。可通過矩陣來描述每個位置發(fā)生的每種活動的情況，但由于在每個位置可以進(jìn)行的活動是有限的，而活動的種類卻是非常多的，因此這個矩陣是非常稀疏的，而進(jìn)行推薦的主要依據(jù)就是矩陣中每個元素的數(shù)值。該文使用基于協(xié)同過濾的協(xié)同矩陣分解方法，利用表示位置與種類關(guān)系的矩陣以及表示活動與活動關(guān)系的矩陣，填補(bǔ)位置—活動矩陣中的缺失項，由此而完成推薦。

3結(jié)束語

由上面的分析可以看出，隨著基于位置的社交網(wǎng)絡(luò)越來越流行，出現(xiàn)了多種多樣的基于位置的服務(wù)，本文根據(jù)這些網(wǎng)絡(luò)中不同形式的位置信息，將所有網(wǎng)絡(luò)進(jìn)行了分類，并給出了每種類型的代表，也進(jìn)行了相關(guān)分析。 隨著對基于位置的社交網(wǎng)絡(luò)的深入研究，產(chǎn)生了許多相關(guān)的應(yīng)用。本文基于用戶和位置兩大主題，對這些應(yīng)用進(jìn)行分類，并詳細(xì)分析了每種應(yīng)用的使用場景及實現(xiàn)原理。

通過分析發(fā)現(xiàn)，目前雖然有一些關(guān)于路徑推薦的應(yīng)用，但推薦的路徑是面向所有用戶的，并沒有考慮用戶的個性化信息，本文還沒有發(fā)現(xiàn)基于位置的社交網(wǎng)絡(luò)中關(guān)于個性化路徑的推薦，如用戶具有商場—餐館—電影院的活動習(xí)慣，如何挖掘出這個習(xí)慣并給用戶推薦符合這個習(xí)慣的路徑，這將是LBSN中又一嶄新應(yīng)用。

參考文獻(xiàn)：

[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.（下轉(zhuǎn)第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.