[發(fā)明專利]在社交網(wǎng)絡(luò)服務(wù)網(wǎng)站中計(jì)算用戶距離的方法和設(shè)備

有效

• 申請(qǐng)?zhí)枺?/td>: 201210025154.7
• 申請(qǐng)日: 2012-01-19
• 公開(kāi)（公告）號(hào): CN103220315B
• 公開(kāi)（公告）日: 2018-01-05
• 發(fā)明（設(shè)計(jì)）人: 趙小菡;王瀟;高婷婷
• 申請(qǐng)（專利權(quán)）人: 北京千橡網(wǎng)景科技發(fā)展有限公司;加州大學(xué)圣塔芭芭拉分校
• 主分類號(hào): H04L29/08
• 分類號(hào): H04L29/08
• 代理公司: 北京市金杜律師事務(wù)所11256
• 代理人: 吳立明

技術(shù)領(lǐng)域

本發(fā)明的實(shí)施方式總體上涉及網(wǎng)絡(luò)信息技術(shù)領(lǐng)域，更具體地，涉及在社交網(wǎng)絡(luò)服務(wù)網(wǎng)站中計(jì)算用戶距離的方法和設(shè)備。

背景技術(shù)

社交網(wǎng)絡(luò)服務(wù)(SNS)網(wǎng)站已經(jīng)發(fā)展為一種重要的網(wǎng)絡(luò)服務(wù)平臺(tái)。通過(guò)SNS網(wǎng)站，用戶可以與其他人進(jìn)行多種形式的交流和互動(dòng)，完成各種各樣的操作。SNS網(wǎng)站是向?qū)μ囟▽?duì)象感興趣或只是一起“閑逛”的人們提供虛擬社區(qū)的web站點(diǎn)。在注冊(cè)和登錄之后，社交網(wǎng)絡(luò)的成員可以通過(guò)語(yǔ)音、聊天、即時(shí)消息、視頻會(huì)議和博客等進(jìn)行通信。社交網(wǎng)絡(luò)通常向成員提供了聯(lián)系其他成員的方法。社交網(wǎng)絡(luò)還可以用作親自會(huì)面的媒介。

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

根據(jù)用戶之間的好友關(guān)系，可以計(jì)算不同用戶在SNS網(wǎng)站中的“距離”。對(duì)于SNS網(wǎng)站中的用戶A和用戶B，二者之間的距離是指從用戶A出發(fā)，沿具有好友連接的其他用戶達(dá)到用戶B所需的最小連接數(shù)目或者跳數(shù)。作為示例，參考圖1A，圖100A表示SNS網(wǎng)站中的用戶連接關(guān)系，頂點(diǎn)A和B分別對(duì)應(yīng)于SNS網(wǎng)站中的用戶A和用戶B。假設(shè)用戶A和B在SNS網(wǎng)站中具有好友關(guān)系，則頂點(diǎn)A與B之間的跳數(shù)為1，即兩個(gè)用戶之間的距離為1。又如，參見(jiàn)圖1B，圖100B同樣表示SNS網(wǎng)站中的用戶關(guān)系。從圖1B中可見(jiàn)，用戶A與B之間沒(méi)有直接的好友連接關(guān)系。此時(shí)，從用戶A出發(fā)沿好友連接到達(dá)B的路徑包括{A，C，B}，{A，C，D，E，B}，{A，D，E，B}，{A，D，C，B}，其中最短路徑為{A，C，B}。因此，用戶A與B之間的好友跳數(shù)為2(即，從A到C，再?gòu)腃到B)，二者之間的距離為2。

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

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

因此，本領(lǐng)域需要一種在SNS網(wǎng)站中更為有效、快速地計(jì)算用戶距離的技術(shù)方案。

發(fā)明內(nèi)容

鑒于以上問(wèn)題，本發(fā)明提出一種在社交網(wǎng)絡(luò)服務(wù)網(wǎng)站中計(jì)算用戶距離的方法和設(shè)備。

在本發(fā)明的一個(gè)方面，提供一種在社交網(wǎng)絡(luò)服務(wù)SNS網(wǎng)站中計(jì)算用戶距離的方法，所述SNS網(wǎng)站包括多個(gè)用戶。所述方法包括：將所述多個(gè)用戶中的每個(gè)用戶映射到坐標(biāo)空間中的點(diǎn)，使得所述多個(gè)用戶中任意兩個(gè)用戶在所述SNS網(wǎng)站中的距離與對(duì)應(yīng)點(diǎn)在所述坐標(biāo)空間中的距離成比例；以及響應(yīng)于計(jì)算所述多個(gè)用戶中的兩個(gè)用戶之間距離的請(qǐng)求，通過(guò)計(jì)算所述兩個(gè)用戶在所述坐標(biāo)空間中的對(duì)應(yīng)點(diǎn)之間的距離，來(lái)計(jì)算所述兩個(gè)用戶之間的距離。

在本發(fā)明的另一方面，提供一種在社交網(wǎng)絡(luò)服務(wù)SNS網(wǎng)站中計(jì)算用戶距離的設(shè)備，所述SNS網(wǎng)站包括多個(gè)用戶，所述設(shè)備包括：映射裝置，配置用于將所述多個(gè)用戶中的每個(gè)用戶映射到坐標(biāo)空間中的點(diǎn)，使得所述多個(gè)用戶中任意兩個(gè)用戶在所述SNS網(wǎng)站中的距離與對(duì)應(yīng)點(diǎn)在所述坐標(biāo)空間中的距離成比例；以及計(jì)算裝置，配置用于響應(yīng)于計(jì)算所述多個(gè)用戶中的兩個(gè)用戶之間距離的請(qǐng)求，通過(guò)計(jì)算所述兩個(gè)用戶在所述坐標(biāo)空間中的對(duì)應(yīng)點(diǎn)之間的距離，來(lái)計(jì)算所述兩個(gè)用戶之間的距離。