[發(fā)明專利]對用戶的好友進(jìn)行分組的方法和裝置

有效

• 申請?zhí)枺?/td>: 201210059885.3
• 申請日: 2012-03-05
• 公開（公告）號: CN102662964A
• 公開（公告）日: 2012-09-12
• 發(fā)明（設(shè)計(jì)）人: 張楠
• 申請（專利權(quán)）人: 北京千橡網(wǎng)景科技發(fā)展有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京市金杜律師事務(wù)所 11256
• 代理人: 吳立明

1.一種用于對用戶的好友進(jìn)行分組的方法，包括：

基于所述用戶的好友列表中多個(gè)好友之間的關(guān)系，生成至少一個(gè)完全子圖；

擴(kuò)張所述至少一個(gè)完全子圖以形成至少一個(gè)團(tuán)；以及

將所述至少一個(gè)團(tuán)之一內(nèi)的好友劃分至一個(gè)分組；

其中所述團(tuán)的連通率不低于第一閾值，所述第一閾值與所述用戶的好友列表中的好友數(shù)量相關(guān)聯(lián)。

2.根據(jù)權(quán)利要求1所述的方法，其中基于所述用戶的好友列表中多個(gè)好友之間的關(guān)系、生成至少一個(gè)完全子圖包括：

基于所述多個(gè)好友各自具有的好友數(shù)量，對所述好友列表中的多個(gè)好友進(jìn)行排序；以及

基于所述排序添加表示所述用戶的好友的點(diǎn)，以生成所述至少一個(gè)完全子圖。

3.根據(jù)權(quán)利要求2所述的方法，其中所述至少一個(gè)完全子圖中的每個(gè)是經(jīng)過補(bǔ)點(diǎn)后的單獨(dú)完全子圖。

4.根據(jù)權(quán)利要求1至3中任一項(xiàng)所述的方法，其中擴(kuò)張所述至少一個(gè)完全子圖以形成至少一個(gè)團(tuán)包括：

向所述至少一個(gè)完全子圖添加表示所述用戶的好友的點(diǎn)以形成擴(kuò)張后的子圖；

基于相似性規(guī)則合并所述擴(kuò)張后的子圖以形成所述至少一個(gè)團(tuán)。

5.根據(jù)權(quán)利要求4所述的方法，其中向所述至少一個(gè)完全子圖添加表示所述用戶的好友的點(diǎn)以形成擴(kuò)張后的子圖包括：如果加入所述點(diǎn)后形成的子圖的連通率不低于第二閾值則添加所述點(diǎn)。

6.根據(jù)權(quán)利要求5所述的方法，還包括：刪除使得所述擴(kuò)張后的子圖的連通率低于第三閾值的點(diǎn)。

7.根據(jù)權(quán)利要求4所述的方法，還包括：從所述多個(gè)團(tuán)中的每個(gè)團(tuán)中刪除使得所述團(tuán)的連通率低于所述第一閾值的點(diǎn)。

8.根據(jù)權(quán)利要求1至3中任一項(xiàng)所述的方法，其中所述第一閾值y表示為：y＝0.6×exp(-0.0035×x)，x表示所述用戶的好友列表中的好友數(shù)量。

9.一種用于對用戶的好友進(jìn)行分組的裝置，包括：

用于基于所述用戶的好友列表中多個(gè)好友之間的關(guān)系，生成至少一個(gè)完全子圖的裝置；

用于擴(kuò)張所述至少一個(gè)完全子圖以形成至少一個(gè)團(tuán)的裝置；以及

用于將所述至少一個(gè)團(tuán)之一內(nèi)的好友劃分至一個(gè)分組的裝置；

其中所述團(tuán)的連通率不低于第一閾值，所述第一閾值與所述用戶的好友列表中的好友數(shù)量相關(guān)聯(lián)。

10.根據(jù)權(quán)利要求9所述的裝置，其中用于基于所述用戶的好友列表中多個(gè)好友之間的關(guān)系、生成至少一個(gè)完全子圖的裝置包括：

用于基于所述多個(gè)好友各自具有的好友數(shù)量、對所述好友列表中的多個(gè)好友進(jìn)行排序的裝置；以及

用于基于所述排序添加表示所述用戶的好友的點(diǎn)、以生成所述至少一個(gè)完全子圖的裝置。

11.根據(jù)權(quán)利要求10所述的裝置，其中所述至少一個(gè)完全子圖中的每個(gè)是經(jīng)過補(bǔ)點(diǎn)后的單獨(dú)完全子圖。

12.根據(jù)權(quán)利要求9至11中任一項(xiàng)所述的裝置，其中用于擴(kuò)張所述至少一個(gè)完全子圖以形成至少一個(gè)團(tuán)的裝置包括：

用于向所述至少一個(gè)完全子圖添加表示所述用戶的好友的點(diǎn)以形成擴(kuò)張后的子圖的裝置；

用于基于相似性規(guī)則合并所述擴(kuò)張后的子圖以形成所述至少一個(gè)團(tuán)的裝置。

13.根據(jù)權(quán)利要求12所述的裝置，其中用于向所述至少一個(gè)完全子圖添加表示所述用戶的好友的點(diǎn)以形成擴(kuò)張后的子圖的裝置包括：用于在加入所述點(diǎn)后形成的子圖的連通率不低于第二閾值時(shí)添加所述點(diǎn)的裝置。

14.根據(jù)權(quán)利要求13所述的裝置，還包括：用于刪除使得所述擴(kuò)張后的子圖的連通率低于第三閾值的點(diǎn)的裝置。

15.根據(jù)權(quán)利要求12所述的裝置，還包括：用于從所述多個(gè)團(tuán)中的每個(gè)團(tuán)中刪除使得所述團(tuán)的連通率低于所述第一閾值的點(diǎn)的裝置。

16.根據(jù)權(quán)利要求9至11中任一項(xiàng)所述的裝置，其中所述第一閾值y表示為：y＝0.6×exp(-0.0035×x)，x表示所述用戶的好友列表中的好友數(shù)量。