具有多种资源类型的资源分配方法和装置

摘要

本说明书实施例提供一种具有多种资源类型的资源分配方法和装置，方法包括：首先获取网络图，网络图包括代表多个实体的多个节点，多个节点中，具有关联关系的节点之间通过边连接；接着提取网络图中的第一联通子图，第一联通子图为连通图，且第一联通子图包括的节点数大于预先确定的不同资源组合的种类数目；其中，每种资源组合中缺失多种资源类型中的至少一种资源类型，或者，每种资源组合中出现多种资源类型中的至少一种资源类型的概率小于预设概率；然后根据第一联通子图中的各节点之间的关联关系，对各节点进行聚群；最后针对第一联通子图中的每个群，为该群内的节点分配资源组合，从而促进不同实体之间的交互。

说明书

技术领域

本说明书一个或多个实施例涉及计算机领域，尤其涉及具有多种资源类型的资源分配方法和装置。

背景技术

对于具有多种资源类型的资源，如何在不同实体之间进行分配，才能更有利于资源的流转，促进不同实体之间的交互，是一个比较常见的问题。

例如，一种卡片收集活动，规则是每个用户可以去收集不同种类的卡片，每参加一次活动，就可以随机获得一张，好友之间可以相互换或赠与卡片。希望使得用户与好友互动起来。

因此，希望能有改进的方案，能够提供一种具有多种资源类型的资源分配方法，促进不同实体之间的交互。

发明内容

本说明书一个或多个实施例描述了一种具有多种资源类型的资源分配方法和装置，能够促进不同实体之间的交互。

第一方面，提供了一种具有多种资源类型的资源分配方法，方法包括：

获取网络图，所述网络图包括代表多个实体的多个节点，所述多个节点中，具有关联关系的节点之间通过边连接；

提取所述网络图中的第一联通子图，所述第一联通子图为连通图，且所述第一联通子图包括的节点数大于预先确定的不同资源组合的种类数目；其中，每种资源组合中缺失所述多种资源类型中的至少一种资源类型，或者，每种资源组合中出现所述多种资源类型中的至少一种资源类型的概率小于预设概率；

根据所述第一联通子图中的各节点之间的关联关系，对各节点进行聚群；

针对所述第一联通子图中的每个群，为该群内的节点分配资源组合。

在一种可能的实施方式中，所述根据所述第一联通子图中的各节点之间的关联关系，对各节点进行聚群，包括：

将所述第一联通子图中度为1的节点和该节点连接的边删除，得到第二联通子图；

根据所述第二联通子图中的各节点之间的关联关系，对各节点进行聚群；

所述针对所述第一联通子图中的每个群，为该群内的节点分配资源组合，包括：

针对所述第二联通子图中的每个群，为该群内的节点分配资源组合。

进一步地，所述针对所述第二联通子图中的每个群，为该群内的节点分配资源组合之后，所述方法还包括：

根据所述第二联通子图中的各节点分配的资源组合的种类，为所述第一联通子图中度为1的节点分配资源组合。

进一步地，所述针对所述第二联通子图中的每个群，为该群内的节点分配资源组合，包括：

针对所述第二联通子图中的每个群，将该群内的各节点按照节点的度由大到小进行排序；

按照排序后的顺序，依次为该群内的各节点分配资源组合。

进一步地，所述按照排序后的顺序，依次为该群内的各节点分配资源组合，包括：

确定与待分配节点具有关联关系的各已分配节点；

当所述各已分配节点分配的资源组合的种类数目小于预先确定的不同资源组合的种类数目时，选择目标资源组合的种类为未分配的资源组合的种类；

为所述待分配节点分配所述目标资源组合。

在一种可能的实施方式中，所述方法还包括：

提取所述网络图中的第三联通子图，所述第三联通子图为连通图，且所述第三联通子图包括的节点数小于或等于预先确定的不同资源组合的种类数目；

针对所述第三联通子图中的各节点，分配资源组合。

进一步地，所述针对所述第三联通子图中的各节点，分配资源组合，包括：

针对所述第三联通子图中的各节点，随机分配不同种类的资源组合。

在一种可能的实施方式中，所述节点代表用户，所述关联关系为好友关系，所述资源为权益。

第二方面，提供了一种具有多种资源类型的资源分配装置，装置包括：

获取单元，用于获取网络图，所述网络图包括代表多个实体的多个节点，所述多个节点中，具有关联关系的节点之间通过边连接；

提取单元，用于提取所述获取单元获取的网络图中的第一联通子图，所述第一联通子图为连通图，且所述第一联通子图包括的节点数大于预先确定的不同资源组合的种类数目；其中，每种资源组合中缺失所述多种资源类型中的至少一种资源类型，或者，每种资源组合中出现所述多种资源类型中的至少一种资源类型的概率小于预设概率；

聚群单元，用于根据所述提取单元提取的第一联通子图中的各节点之间的关联关系，对各节点进行聚群；

分配单元，用于针对所述聚群单元得到的第一联通子图中的每个群，为该群内的节点分配资源组合。

第三方面，提供了一种计算机可读存储介质，其上存储有计算机程序，当所述计算机程序在计算机中执行时，令计算机执行第一方面的方法。

第四方面，提供了一种计算设备，包括存储器和处理器，所述存储器中存储有可执行代码，所述处理器执行所述可执行代码时，实现第一方面的方法。

通过本说明书实施例提供的方法和装置，首先获取网络图，所述网络图包括代表多个实体的多个节点，所述多个节点中，具有关联关系的节点之间通过边连接；接着提取所述网络图中的第一联通子图，所述第一联通子图为连通图，且所述第一联通子图包括的节点数大于预先确定的不同资源组合的种类数目；其中，每种资源组合中缺失所述多种资源类型中的至少一种资源类型，或者，每种资源组合中出现所述多种资源类型中的至少一种资源类型的概率小于预设概率；然后根据所述第一联通子图中的各节点之间的关联关系，对各节点进行聚群；最后针对所述第一联通子图中的每个群，为该群内的节点分配资源组合。本说明书实施例中，能够尽量为具有关联关系的节点分配不同的资源组合，从而促进不同实体之间的交互。

附图说明

为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其它的附图。

图1为本说明书披露的一个实施例的实施场景示意图；

图2示出根据一个实施例的具有多种资源类型的资源分配方法流程图；

图3为本说明书实施例提供的一种网络图的结构示意图；

图4示出根据另一个实施例的具有多种资源类型的资源分配方法流程图；

图5示出根据一个实施例的具有多种资源类型的资源分配装置的示意性框图。

具体实施方式

下面结合附图，对本说明书提供的方案进行描述。

图1为本说明书披露的一个实施例的实施场景示意图。该实施场景涉及具有多种资源类型的资源分配方法，该方法用于对于具有多种资源类型的资源，在不同实体之间进行分配，提出解决方案，以利于资源的流转，促进不同实体之间的交互。其中，资源可以为实体资源或虚拟资源，实体可以为个人或单位。

参见图1所示的实施场景，一种卡片收集活动，规则是每个用户可以去收集不同种类的卡片，每参加一次活动，就可以随机获得一张，好友之间可以相互换或赠与卡片。希望每个用户尽可能会缺一种卡片，好友之间缺的卡片不同，进而使得用户与好友互动起来。

本说明书实施例中，假定卡片共有五种类型，分别为，卡片A、卡片B、卡片C、卡片D和卡片E。为了让用户尽可能会缺一种卡片，先生成K种礼物包，每种礼物包里面都会有至少一种卡片缺失或至少一种卡片出现概率很低，例如，礼物包1{卡片A、卡片B、卡片C、卡片D}，该礼物包1中缺失卡片E；礼物包2{卡片A、卡片B、卡片C、卡片E}，该礼物包2中缺失卡片D。在用户参加活动时，从分配给该用户的礼物包中选择一种卡片，将该卡片分配给该用户，从而该用户会有至少一种卡片缺失或较大概率的出现至少一种卡片缺失，例如，为用户甲分配礼物包1，当用户甲参加活动时，其得到的卡片只能是礼物包1中的一种卡片，因此用户甲会缺失卡片E；为用户乙分配礼物包2，当用户乙参加活动时，其得到的卡片只能是礼物包2中的一种卡片，因此用户乙会缺失卡片D。如果用户甲和用户乙互为好友，则二者可以通过交换卡片，从而集齐五种卡片。

本说明书实施例中，为了促进好友之间的互动，希望每个人发的礼物包和他的好友发的尽可能的不同，求一种好的礼物包的分配方案。这个问题抽象出来，一共有N个人，两两存在好友关系，目前有K种礼物包要发给这些人，要求是每个人发的礼物包和他的好友发的尽可能的不同，求一种好的礼物包的分配方案。这里，针对好友关系，建立一个好友图网络，假设每个节点代表一个人，好友关系代表两个节点之间的边。接下来，将采用图计算的方法来求解这个问题。该方法，能够实现最大可能的满足好友之间分配的礼物包尽可能不同，从而促进好友之间的交互。

可以理解的是，上述实施场景仅为本说明书实施例的一种可能的应用场景，并不用于对本说明书实施例实施场景的限定。

图2示出根据一个实施例的具有多种资源类型的资源分配方法流程图，该方法可以基于图1所示的实施场景。如图2所示，该实施例中具有多种资源类型的资源分配方法包括以下步骤：步骤21，获取网络图，所述网络图包括代表多个实体的多个节点，所述多个节点中，具有关联关系的节点之间通过边连接；步骤22，提取所述网络图中的第一联通子图，所述第一联通子图为连通图，且所述第一联通子图包括的节点数大于预先确定的不同资源组合的种类数目；其中，每种资源组合中缺失所述多种资源类型中的至少一种资源类型，或者，每种资源组合中出现所述多种资源类型中的至少一种资源类型的概率小于预设概率；步骤23，根据所述第一联通子图中的各节点之间的关联关系，对各节点进行聚群；步骤24，针对所述第一联通子图中的每个群，为该群内的节点分配资源组合。下面描述以上各个步骤的具体执行方式。

首先在步骤21，获取网络图，所述网络图包括代表多个实体的多个节点，所述多个节点中，具有关联关系的节点之间通过边连接。

在一个示例中，所述节点代表用户，所述关联关系为好友关系，所述资源为权益。

图3为本说明书实施例提供的一种网络图的结构示意图，参照图3，该网络图包括节点1至节点16，其中，两个节点之间的边代表两个节点具有好友关系，例如，节点2与节点1、节点3和节点10分别具有好友关系，节点2与其他节点均不具有好友关系；节点9只与节点3具有好友关系，与其他节点均不具有好友关系。

接着在步骤22，提取所述网络图中的第一联通子图，所述第一联通子图为连通图，且所述第一联通子图包括的节点数大于预先确定的不同资源组合的种类数目；其中，每种资源组合中缺失所述多种资源类型中的至少一种资源类型，或者，每种资源组合中出现所述多种资源类型中的至少一种资源类型的概率小于预设概率。

联通子图：一般的，原始的网络图可以切割成若干个“小图”，如果其中任意一个“小图”里面的任意两个节点都是可达的，则称作每一个“小图”为连通图，该“小图”可以称为网络图的联通子图。例如，图3中包括联通子图31和联通子图32，若预先确定的不同资源组合的种类数目为5，则联通子图31为第一联通子图。

然后在步骤23，根据所述第一联通子图中的各节点之间的关联关系，对各节点进行聚群。

图聚群：针对一个网络图，假设每个节点代表一个用户，那么将用户网络分割成若干个部分，每个部分看作是一个聚群，而每个用户则归属于其中的某个聚群。一般的，希望相关度高的节点尽可能的聚在同一个聚群中，常见的聚群算法有k-means等。

在一个示例中，将所述第一联通子图中度为1的节点和该节点连接的边删除，得到第二联通子图；根据所述第二联通子图中的各节点之间的关联关系，对各节点进行聚群。

度(Degree)：一个节点的度是指与该节点相关联的边的条数。参照图3，节点1的度为7，节点9的度为1。

最后在步骤24，针对所述第一联通子图中的每个群，为该群内的节点分配资源组合。

在一个示例中，针对所述第二联通子图中的每个群，为该群内的节点分配资源组合。

进一步地，所述针对所述第二联通子图中的每个群，为该群内的节点分配资源组合之后，根据所述第二联通子图中的各节点分配的资源组合的种类，为所述第一联通子图中度为1的节点分配资源组合。

进一步地，针对所述第二联通子图中的每个群，将该群内的各节点按照节点的度由大到小进行排序；按照排序后的顺序，依次为该群内的各节点分配资源组合。

进一步地，确定与待分配节点具有关联关系的各已分配节点；当所述各已分配节点分配的资源组合的种类数目小于预先确定的不同资源组合的种类数目时，选择目标资源组合的种类为未分配的资源组合的种类；为所述待分配节点分配所述目标资源组合。参照图3，若资源组合的种类包括种类1、种类2、种类3、种类4、种类5共五种，若待分配节点为节点9，确定与节点9具有关联关系的已分配节点为节点3；为节点3分配的资源组合的种类为种类2，已分配节点分配的资源组合的种类数目1小于预先确定的不同资源组合的种类数目5，选择目标资源组合的种类为未分配的资源组合的种类，例如种类1或种类3或种类4或种类5。

在一个示例中，提取所述网络图中的第三联通子图，所述第三联通子图为连通图，且所述第三联通子图包括的节点数小于或等于预先确定的不同资源组合的种类数目；针对所述第三联通子图中的各节点，分配资源组合。例如，图3中包括联通子图31和联通子图32，若预先确定的不同资源组合的种类数目为5，则联通子图32为第三联通子图。

进一步地，针对所述第三联通子图中的各节点，随机分配不同种类的资源组合。

通过本说明书实施例提供的方法，首先获取网络图，所述网络图包括代表多个实体的多个节点，所述多个节点中，具有关联关系的节点之间通过边连接；接着提取所述网络图中的第一联通子图，所述第一联通子图为连通图，且所述第一联通子图包括的节点数大于预先确定的不同资源组合的种类数目；其中，每种资源组合中缺失所述多种资源类型中的至少一种资源类型，或者，每种资源组合中出现所述多种资源类型中的至少一种资源类型的概率小于预设概率；然后根据所述第一联通子图中的各节点之间的关联关系，对各节点进行聚群；最后针对所述第一联通子图中的每个群，为该群内的节点分配资源组合。本说明书实施例中，能够尽量为具有关联关系的节点分配不同的资源组合，从而促进不同实体之间的交互。

图4示出根据另一个实施例的具有多种资源类型的资源分配方法流程图，该方法可以基于图1所示的实施场景。如图4所示，该实施例中具有多种资源类型的资源分配方法包括以下步骤：

步骤1，建立好友网络。

提取好友关系数据，将每个人看作是一个节点，存在好友关系的之间建议一条边。这样就可以构造成一个好友网络。

步骤2，联通图发现。

由于好友网络的数据往往非常大，而且针对本问题也会采取不同的解决策略，因此这里先进行联通图发现。这一步的输入是网络图，输出是每个节点对应的联通子图的标号。根据标号，可以计算每个子图中的节点个数。

步骤3.1&步骤3.2，提取联通子图。

这里按照每个联通图的节点个数，进行数据分流，以便后续不同的操作。对于节点数小于K的子图，划分在一起；剩余的，划分在一起。其中，节点数等于K的子图可以与节点数小于K的子图，划分在一起，注意，前文假设了一共有K种礼物包，每种礼物包里面都会有至少一种卡片缺失或至少一种卡片出现概率很低。

步骤4.1，子图内随机发放礼物包。

对于节点数小于或等于K的联通子图，在每一个联通子图中的节点，每次随机取出一种礼物包进行发放(发放过的礼物包在同一个联通子图中不可以再次发放)，由于总的礼物包的种类为K，因此在一个联通子图中，必然每个人收到的礼物包是不同的，也就保证了互缺卡片。

步骤4.2&步骤4.3，提取网络内度为1的点和边；提取剩余的点和边：

这里将步骤3.2中提取的联通子图进行拆分，把度为1的点和边取出来，剩余的点和边构成一个新的网络。如果新网络的节点的礼物包确定了，那么和他们本来相邻的度为1的节点的礼物包就很容易确定了。

步骤5，进行聚群，礼物包初分配。

由于原本步骤4.3中产生的网络图节点个数依旧很大，因此先进行图聚群，即把一个大图分割成很多个小图，常见的算法，比如k-means等；然后，在每个小图中确定每个节点分配的礼物包。在每个小图中，按照节点的度进行排序(从大到小)，然后依次分配礼物包，每次分配礼物包的时候，尽可能的分配和其周边节点不同的礼物包。

步骤6，确定度为1节点的礼物包分配。

在前述步骤5完成之后，也即步骤4.3中得到的网络图的节点都已经分配了礼物包，那么就可以根据步骤4.2中的度为1的节点的边连接关系，确定最后度为1的节点的礼物包的分配了。具体的，只要是度为1的节点的礼物包与其相邻的节点的礼物包不相同即可。

本说明书实施例提供了一种卡片的分发方法，可以使得用户之间更加的活跃的互换或赠送卡片。

根据另一方面的实施例，还提供一种具有多种资源类型的资源分配装置，该装置用于执行本说明书实施例提供的具有多种资源类型的资源分配方法。图5示出根据一个实施例的具有多种资源类型的资源分配装置的示意性框图。如图5所示，该装置500包括：

获取单元51，用于获取网络图，所述网络图包括代表多个实体的多个节点，所述多个节点中，具有关联关系的节点之间通过边连接；

提取单元52，用于提取所述获取单元51获取的网络图中的第一联通子图，所述第一联通子图为连通图，且所述第一联通子图包括的节点数大于预先确定的不同资源组合的种类数目；其中，每种资源组合中缺失所述多种资源类型中的至少一种资源类型，或者，每种资源组合中出现所述多种资源类型中的至少一种资源类型的概率小于预设概率；

聚群单元53，用于根据所述提取单元52提取的第一联通子图中的各节点之间的关联关系，对各节点进行聚群；

分配单元54，用于针对所述聚群单元53得到的第一联通子图中的每个群，为该群内的节点分配资源组合。

可选地，作为一个实施例，所述聚群单元53，具体用于：

将所述第一联通子图中度为1的节点和该节点连接的边删除，得到第二联通子图；

根据所述第二联通子图中的各节点之间的关联关系，对各节点进行聚群；

所述分配单元，具体用于：

针对所述第二联通子图中的每个群，为该群内的节点分配资源组合。

进一步地，所述分配单元54，还用于在所述针对所述第二联通子图中的每个群，为该群内的节点分配资源组合之后，根据所述第二联通子图中的各节点分配的资源组合的种类，为所述第一联通子图中度为1的节点分配资源组合。

进一步地，所述分配单元54，具体包括：

排序子单元，用于针对所述第二联通子图中的每个群，将该群内的各节点按照节点的度由大到小进行排序；

分配子单元，用于按照排序后的顺序，依次为该群内的各节点分配资源组合。

进一步地，所述分配子单元，具体用于：

确定与待分配节点具有关联关系的各已分配节点；

当所述各已分配节点分配的资源组合的种类数目小于预先确定的不同资源组合的种类数目时，选择目标资源组合的种类为未分配的资源组合的种类；

为所述待分配节点分配所述目标资源组合。

可选地，作为一个实施例，所述提取单元52，还用于提取所述网络图中的第三联通子图，所述第三联通子图为连通图，且所述第三联通子图包括的节点数小于或等于预先确定的不同资源组合的种类数目；

所述分配单元54，还用于针对所述第三联通子图中的各节点，分配资源组合。

进一步地，所述分配单元54，具体用于针对所述第三联通子图中的各节点，随机分配不同种类的资源组合。

可选地，作为一个实施例，所述节点代表用户，所述关联关系为好友关系，所述资源为权益。

通过本说明书实施例提供的装置，首先获取单元51获取网络图，所述网络图包括代表多个实体的多个节点，所述多个节点中，具有关联关系的节点之间通过边连接；接着提取单元52提取所述网络图中的第一联通子图，所述第一联通子图为连通图，且所述第一联通子图包括的节点数大于预先确定的不同资源组合的种类数目；其中，每种资源组合中缺失所述多种资源类型中的至少一种资源类型，或者，每种资源组合中出现所述多种资源类型中的至少一种资源类型的概率小于预设概率；然后聚群单元53根据所述第一联通子图中的各节点之间的关联关系，对各节点进行聚群；最后分配单元54针对所述第一联通子图中的每个群，为该群内的节点分配资源组合。本说明书实施例中，能够尽量为具有关联关系的节点分配不同的资源组合，从而促进不同实体之间的交互。

根据另一方面的实施例，还提供一种计算机可读存储介质，其上存储有计算机程序，当所述计算机程序在计算机中执行时，令计算机执行结合图2或图4所描述的方法。

根据再一方面的实施例，还提供一种计算设备，包括存储器和处理器，所述存储器中存储有可执行代码，所述处理器执行所述可执行代码时，实现结合图2或图4所描述的方法。

本领域技术人员应该可以意识到，在上述一个或多个示例中，本发明所描述的功能可以用硬件、软件、固件或它们的任意组合来实现。当使用软件实现时，可以将这些功能存储在计算机可读介质中或者作为计算机可读介质上的一个或多个指令或代码进行传输。

以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施方式而已，并不用于限定本发明的保护范围，凡在本发明的技术方案的基础之上，所做的任何修改、等同替换、改进等，均应包括在本发明的保护范围之内。