对用户的好友进行分组的方法和装置的制作方法.docx

对用户的好友进行分组的方法和装置的制作方法专利名称：对用户的好友进行分组的方法和装置的制作方法技术领域：本发明的各实施方式涉及社交网络，并且更具体地，涉及ー种对用户的好友进行分组的方法和装置背景技术：随着网络技术的发展而出现了诸如社交网络的众多网络应用，在社交网络中，一个用户可以具有多个好友，这些好友可以包括小学同学、中学同学、大学同学、同事、家人等各种复杂的社会关系如果用户只具有较少数量的好友，一般可以在ー个统一列表中显示全部好友然而，当用户的好友数量达到一定数量级(例如，数十甚至上百人)时，在ー个列表中维护好友信息将会变得混乱，例如出现难以找到特定好友等问题越来越多的用户倾向于采用分组方式管理好友，例如，可以为小学同学、中学同学、大学同学等不同人群建立単独的分组，以便于管理好友在现有技术中，创建分组和确定向该分组中加入哪些好友都是用户手工完成的用户需要人工创建分组并将未分组的好友逐个加入相应的分组，从而实现分类管理的目的这是ー项枯燥的过程发明内容基于现有技术中的上述缺陷，期望能够提供一种自动对用户的好友进行分组的方法，并且期望该方法能够辅助用户将自己的好友进行分类在需要时，用户还可以基于自动获得的分组进行调整，例如向分组添加好友或者删除好友。

根据本发明的一个实施方式，提供了一种用于对用户的好友进行分组的方法，包括基于用户的好友列表中多个好友之间的关系，生成至少ー个完全子图；扩张至少ー个完全子图以形成至少ー个团；以及将至少一个团之一内的好友划分至一个分组；其中团的连通率不低于第一阈值,第一阈值与用户的好友列表中的好友数量相关联根据本发明的另ー实施方式，基于用户的好友列表中多个好友之间的关系、生成至少ー个完全子图包括基于多个好友各自具有的好友数量，对好友列表中的多个好友进行排序；以及基于排序添加表示用户的好友的点，以生成至少ー个完全子图根据本发明的另ー实施方式，提供了一种用于对用户的好友进行分组的装置，包括用于基于用户的好友列表中多个好友之间的关系，生成至少ー个完全子图的装置；用于扩张至少ー个完全子图以形成至少ー个团的装置；以及用于将至少ー个团之ー内的好友划分至一个分组的装置；其中团的连通率不低于第一阈值，第一阈值与用户的好友列表中的好友数量相关联根据本发明的另ー实施方式，用于基于用户的好友列表中多个好友之间的关系、生成至少ー个完全子图的装置包括用于基于多个好友各自具有的好友数量，对好友列表中的多个好友进行排序的装置；以及用于基于排序添加表示用户的好友的点，以生成至少ー个完全子图的装置。

采用本发明的各实施方式，提供了一种对用户的好友进行自动分组的方法和装置，以取代用户对众多好友进行手工分组的操作用户还可以在自动分组的基础上进行调整，以便对分组进行细化处理结合附图并參考以下详细说明，本发明各实施方式的特征、优点及其他方面将变得更加明显，在此以示例性而非限制性的方式示出了本发明的若干实施方式在附图中图I示意性示出了社交网络中好友之间的关系的图示； 图2示意性示出了根据本发明一个实施方式的对用户的好友进行分组的方法的流程图；图3示意性示出了根据本发明一个实施方式的生成完全子图的方法的流程图；图4示意性示出了根据本发明一个实施方式的在生成完全子图期间的各子图的示意图；图5A和图5B分别示意性示出了根据本发明一个实施方式的向团中添加点以进行扩张的示意图；图6A和图6B分别示意性示出了根据本发明一个实施方式的合并相似子图前后的图示；图7示意性示出了根据本发明一个实施方式的计算第一阈值的函数图示；图8示意性示出了根据本发明一个实施方式的对用户的好友进行分组的装置的结构图；以及图9示出了适于用来实践本发明实施方式的计算机系统的示意性框图具体实施例方式下面參考附图详细描述本发明的各实施方式。

附图中的流程图和框图，图示了按照本发明各种实施方式的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作在这点上，流程图或框图中的每个方框可以代表一个模块、程序段、或代码的一部分，所述模块、程序段、或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令也应当注意，在有些作为备选的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生例如，两个接连地表示的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现下面将參考若干示例性实施方式来描述本发明的原理和精神应当理解，给出这些实施方式仅仅是为了使本领域技术人员能够更好地理解进而实现本发明，而并非以任何方式限制本发明的范围为方便下文描述，首先介绍本申请中技术术语的定义在此使用的术语“社交网络”或者“社交网站”是指向对特定对象感兴趣或只是ー起“闲逛”的人们提供虚拟社区的web站点成员通过语音、聊天、即时消息、视频会议和博客等技术手段进行通信。

而且，社交网络通常向成员提供联系其他成员的好友的方法这种站点还可以用作亲自会面的媒介社交网络为其用户或成员提供与该社交网络的其他用户进行通信和交互的能力(注意，在社交网络的“成员”和“用户”具有等同的含义，因此可互換使用)在操作中，社交网络的用户可以首先进行登录，继而与其好友或者其他用户进行互动在此使用的术语“好友”是指用户通过社交网络形成有连接、关联或者其他关系的任何其他用户社交网络中的连接通常是双向的(但不是必须的)，因此术语“好友”可能依赖于參照系注意，好友之间的连接可以是直接连接；然而，社交网络的某些实施方式允许经由一级或者多级间接连接而形成好友关系另外，术语“好友”并非必须要求用户在现实生活中实际上是朋友，它仅仅表示社交网络中的关系然而应当注意，在本发明中，当好友在真实世界中彼此相识时，这两个好友在社交网络中通常具有好友关系在本发明的实施方式中并不特意区分相识、具有好友关系以及在表示好友的节点之间具有边，另外以节点表示好友，也并不特意区分好友和节点在下文中，将仅以社交网络中的用户如何对自己的好友进行分组，来具体说明如何实现本发明的方法和装置图I示意性示出了社交网络中好友之间的关系的图示100。

应当注意，图I示出 的是特定用户的好友，也即在该用户的好友列表中的好友在图I中，以节点表示用户的好友，而以节点之间的边表示好友之间的关系例如，节点102和104之间存在边，这表示好友102和104彼此之间是好友；节点102和106之间没有边，这表示好友102和106之间不具有好友关系本发明进行分组时所基于的ー个原理在于，位于同一分组内的好友之间通常彼此相识，并且相识的好友通常在社交网络中具有好友关系例如“中学同学”分组中的好友通常是中学同班或者同年级同学，通常他们会彼此“添加好友”反映到关系图中，表示彼此相识的好友的节点之间具有边，因而可以基于关系图中由节点和边构成的“团”来对好友进行分组例如对于图I所示的关系图，节点102、104、108、110和112构成全连通子图，即，在上述节点中任何一对节点之间都具有边这表示，由上述节点表示的5个好友之间分别具有好友关系，因而可以将这5个好友划分在一个分组内又例如，对于节点106，该节点仅与节点112和110分别具有边，因而可以认为用户106不太可能与上述5个彼此相识的好友属于同一类应当注意，本发明中所述的“团”是指用户好友的关系图中的子图，并且该子图的连通率满足特定的阈值。

连通率表示一个图或子图中存在的边的数量与在任意两个节点间均具有边时边的数量的比值例如，对于由节点102、104、108、110和112构成的子图(图I中虚线左侧的部分)连通率=^^ = 1，即此时为全连通子图又例如，对于整个图I :连通率=_1 _ = 0.86x5/2根据本发明的一个实施方式，示出了一种用于对用户的好友进行分组的方法，包括基于用户的好友列表中多个好友之间的关系，生成至少ー个完全子图；扩张至少ー个完全子图以形成至少ー个团；以及将至少一个团之一内的好友划分至一个分组；其中团的连通率不低于第一阈值,第一阈值与用户的好友列表中的好友数量相关联下面參见图2详细描述，图2示意性示出了根据本发明一个实施方式的对用户的好友进行分组的方法的流程图200在步骤S202中，基于用户的好友列表中多个好友之间的关系，生成至少ー个完全子图在此，可以以每个好友注册时的标识符(例如，注册号)来作为关系图中的节点标识注册号越小则该用户的注册时间越早，可以认为注册号较小的用户因使用时间较长而具有较高优先级，或者还可以采用其他规则区分用户的优先级提取完全子图的目的在于将完全子图作为寻找“团”的起点，因为完全子图内的好友彼此都相识，因而以此为基础更易于获得正确性较高的分组。

在步骤S204中，扩张至少ー个完全子图以形成至少ー个团应当注意，此处的团的连通率不低于第一阈值，第一阈值与用户的好友列表中的好友数量相关联根据本发明的一个实施方式，将对好友进行分组的问题转换为在关系图中寻找连通率满足特定要求的团，以保证该团内的好友之间基本上彼此都是相识的 例如，基于用户对好友分组准确程度的要求，可以取O. 7-0. 8之间的值来作为第ー阈值，该第一阈值越高则准确分组的可能性越高，反之则越低如果用户仅希望粗略地对好友进行分类，还可以选择更低的第一阈值，如果希望准确分组则可以选取高于O. 8的第ー阈值继而在步骤S206中，将至少一个团之一内的好友划分至ー个分组经过步骤S202和S204后获得的团已经保证了其中的好友基本上都彼此相识，因而将团内的好友划分至一个分组即可实现将好友分类应当注意，可以形成一个或者多个团，可以仅将ー个团内的好友划分至一个分组，还可以将多个或者全部团内的好友分别划分至相应的分组根据本发明的一个实施方式，基于用户的好友列表中多个好友之间的关系、生成至少ー个完全子图包括基于多个好友各自具有的好友数量，对好友列表中的多个好友进行排序；以及基于排序添加表示用户的好友的点，以生成至少ー个完全子图。

基于用户的好友自身具有好友的数量来对好友列表进行排序目的在于，在生成完全子图时首先考虑自身好友数量较多的好友，以加快生成完全子图的速度当列表中两个好友自身的好友数量相等时，可以对注册号较小的用户赋予较高优先级基于另一策略，如果经统计发现新注册的用户在近期使用社交网络的频率更高，还可以对注册号较大的用户赋予较高优先级根据排序后的好友列表来向关系图(最初为空)中逐个添加表示好友的节点图3示意性示出了根据本发明一个实施方式的生成完全子图的方法的流程图300在初始时完全子图为空，通过遍历排序后列表中的每个好友来添加表示好友的节点在步骤S302中，按照排序后好友列表的顺序加入ー个好友在步骤S304中，判断当前好友是否与某个子图构成完全图如果判断结果为是，则在步骤S306将当前好友加入该子图，否则在步骤S308利用当前好友形成単独子图(此时仅包括表示当前好友的ー个节点)在步骤S310中，如果存在下一好友，则操作流程返回至步骤S302，否则结束在本发明的一个实施方式中，至少ー个完全子图中的每个是经过补点后的单独完全子图在此“补点”是指为保留好友之间的关系而额外添加点的过程在经过图3所示步骤之后，还可能存在孤立节点的情况并且这有可能导致丢失某些完全子图，因而需要进行“补点”的操作。

图4示意性示出了根据本发明一个实施方式的在生成完全子图期间的各子图的示意图400图4A示出了表示好友402、404、406和408之间的真实好友关系的图示；图4B示出了经过图3所示步骤后形成的关系图400B例如节点402、404、406位于排序后好友队列的前端，因而首先形成了左侧三角形的完全子图尽管节点408与节点402和406也能形成完全子图，然而根据步骤S304，由于将节点408加入左侧。