面向移動社會網絡的好友推薦方法

王珊珊　冷甦鵬

摘要：

針對移動社會網絡（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.