基于位置的社交網絡研究綜述

朱立超　李治軍　姜守旭

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

關鍵詞：基于位置的社交網絡； 位置信息； 推薦

中圖分類號：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.