[發明專利]在社交網絡服務網站中計算用戶距離的方法和設備

有效

• 申請號: 201210025154.7
• 申請日: 2012-01-19
• 公開（公告）號: CN103220315B
• 公開（公告）日: 2018-01-05
• 發明（設計）人: 趙小菡;王瀟;高婷婷
• 申請（專利權）人: 北京千橡網景科技發展有限公司;加州大學圣塔芭芭拉分校
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 北京市金杜律師事務所11256
• 代理人: 吳立明

技術領域

本發明的實施方式總體上涉及網絡信息技術領域，更具體地，涉及在社交網絡服務網站中計算用戶距離的方法和設備。

背景技術

社交網絡服務(SNS)網站已經發展為一種重要的網絡服務平臺。通過SNS網站，用戶可以與其他人進行多種形式的交流和互動，完成各種各樣的操作。SNS網站是向對特定對象感興趣或只是一起“閑逛”的人們提供虛擬社區的web站點。在注冊和登錄之后，社交網絡的成員可以通過語音、聊天、即時消息、視頻會議和博客等進行通信。社交網絡通常向成員提供了聯系其他成員的方法。社交網絡還可以用作親自會面的媒介。

當一個人向SNS網站進行了注冊并且可能還通過了相關認認證之后，他/她稱為該SNS網站的“用戶”或“成員”。在SNS網站中，不同的用戶之間可以建立連接或關聯關系，這種關聯關系在SNS網站中通常被稱為“好友關系”或簡稱“好友”。由于SNS網站中的連接通常是雙向的(但這不是必須的)，因此術語“好友”可能依賴于參照系。而且，用戶之間的連接可以是直接連接；但是用戶之間的一級或者多級間接連接也是允許的。可以理解，SNS網站中的“好友”并非必須要求用戶在現實生活中實際上是朋友，它僅僅表示SNS網站中的關系。

根據用戶之間的好友關系，可以計算不同用戶在SNS網站中的“距離”。對于SNS網站中的用戶A和用戶B，二者之間的距離是指從用戶A出發，沿具有好友連接的其他用戶達到用戶B所需的最小連接數目或者跳數。作為示例，參考圖1A，圖100A表示SNS網站中的用戶連接關系，頂點A和B分別對應于SNS網站中的用戶A和用戶B。假設用戶A和B在SNS網站中具有好友關系，則頂點A與B之間的跳數為1，即兩個用戶之間的距離為1。又如，參見圖1B，圖100B同樣表示SNS網站中的用戶關系。從圖1B中可見，用戶A與B之間沒有直接的好友連接關系。此時，從用戶A出發沿好友連接到達B的路徑包括{A，C，B}，{A，C，D，E，B}，{A，D，E，B}，{A，D，C，B}，其中最短路徑為{A，C，B}。因此，用戶A與B之間的好友跳數為2(即，從A到C，再從C到B)，二者之間的距離為2。

在SNS網站中，任意給出兩個用戶，快速、準確地確定他們之間的距離是有益的。這例如可以用于好友推薦、用戶群組劃分、提供個性化服務等等多個方面。現有技術中，通常根據圖(graph)來計算用戶之間的距離。具體而言，可以將SNS網站中的每個用戶作為頂點，如果兩個用戶之間具有直接好友關系(即，距離為1)，則對應的兩個頂點之間存在邊。以此方式，可以利用一個無向圖來代表SNS網站中的用戶關系。此后，為了計算任何給定用戶之間的距離，只需計算圖中對應頂點的距離即可。這通常是通過對圖執行廣度優先搜索(BFS)實現的。

這種方法對于數據規模較小的情況比較方便有效，但是難以處理用戶數量眾多的大規模SNS網站。例如，中大規模的SNS網站通常擁有數百萬、數千萬乃至數以億計的用戶，并且用戶之間具有復雜的相互關系。在這種情況下，利用圖的BFS確定用戶距離在計算復雜性、響應時間、資源成本等方面都是很高的，甚至是不可行的。可以理解，一方面，如果計算并且存儲所有用戶之間的距離，在計算復雜性以及存儲資源上都會給系統造成巨大壓力。另一方面，如果實時地根據圖的BFS來計算用戶之間的距離，則很難滿足實時響應的要求。

因此，本領域需要一種在SNS網站中更為有效、快速地計算用戶距離的技術方案。

發明內容

鑒于以上問題，本發明提出一種在社交網絡服務網站中計算用戶距離的方法和設備。

在本發明的一個方面，提供一種在社交網絡服務SNS網站中計算用戶距離的方法，所述SNS網站包括多個用戶。所述方法包括：將所述多個用戶中的每個用戶映射到坐標空間中的點，使得所述多個用戶中任意兩個用戶在所述SNS網站中的距離與對應點在所述坐標空間中的距離成比例；以及響應于計算所述多個用戶中的兩個用戶之間距離的請求，通過計算所述兩個用戶在所述坐標空間中的對應點之間的距離，來計算所述兩個用戶之間的距離。

在本發明的另一方面，提供一種在社交網絡服務SNS網站中計算用戶距離的設備，所述SNS網站包括多個用戶，所述設備包括：映射裝置，配置用于將所述多個用戶中的每個用戶映射到坐標空間中的點，使得所述多個用戶中任意兩個用戶在所述SNS網站中的距離與對應點在所述坐標空間中的距離成比例；以及計算裝置，配置用于響應于計算所述多個用戶中的兩個用戶之間距離的請求，通過計算所述兩個用戶在所述坐標空間中的對應點之間的距離，來計算所述兩個用戶之間的距離。