本发明涉及网络技术领域，特别是涉及一种确定最大影响程度指标的种子集合的方法及装置。
背景技术：
随着网络技术的发展，越来越多的产品需要依靠网络传播达到宣传的目的，病毒式传播因为在网络环境中用户依靠自身的激活力，以“病毒式”传播产品而得到商家的钟爱。
病毒式传播是第一个用户开始，依靠第一个用户自发的宣传产品，以激活其他用户去购买或者宣传，从而达到滚雪球式的产品传播效果。示例性的，当一个手机产品需要宣传时，会选择一些有影响程度指标的用户，这些有影响程度指标的用户称为种子用户，利用种子用户宣传该手机产品，从而激活与种子用户有交际的用户购买或者宣传该手机产品，依靠这些与种子用户有交际的用户从而激活其他用户购买或者宣传该手机产品。
病毒式传播的主要问题是在产品宣传传播过程中，如何使得目标产品传播的影响程度指标最大。随着广告竞争需求的复杂化，网络环境中同时也存在竞争者，即宣传产品的竞品，而竞品广告商也会选择一些种子用户宣传自己的产品，此种情况下，在网络中宣传产品，如何将目标产品传播的影响程度指标成为最大，变得更加复杂。
现有技术中通过模拟网路环境以及用户之间的关系，构建给定网络，使用独立级联模型，将该给定网络抽象为一个有向图g，如图1所示，有向图g中包含各个用户节点v，例如1至12，以及用户节点与用户节点之间的有向边e，每个有向边对应一个激活概率，一个用户节点沿着有向边的方向，服从该有向边对应的激活概率以激活另一个用户节点，例如：0至1之间的有向边可以表示为有向箭头，当竞争对手的种子集合和目标产品的种子集合大小k给定时，在该有向图g随机选择起始用户节点，然后在该有向图g中模拟产品的传播过程，传播过程为：竞争对手的种子集合给定的情况下，随机选择起始节点，起始节点服从第一激活概率激活与起始节点相邻的第一节点，第一激活概率为起始节点与第一节点之间有向边的概率，例如，生成小于1的随机数，当随机数小于第一激活概率，则确定第一节点被起始节点激活，当第一节点被成功激活时，第一节点服从第二激活概率激活与第一节点相邻的第二节点，第二激活概率为第一节点与第二节点之间有向边的概率，直至轮询所有节点。将k个被激活的节点作为目标种子集合中的目标节点，将目标种子集合的影响力与竞争对手的种子集合的影响力的差值最大化作为目标函数，然后重复模拟传播过程，在被成功激活的目标节点中，选择使得目标函数最大的目标节点，直至目标种子集合中的目标节点的个数达到k，得到目标种子集合。
由于现有技术中，需要重复模拟产品的传播过程才能确定目标种子集合，而一个传播过程的时间较长，因此确定目标种子集合的时间较长。
技术实现要素：
本发明实施例的目的在于提供一种确定最大影响程度指标的种子集合的方法及装置，以减少在确定目标种子集合过程中花费的时间。具体技术方案如下：
第一方面，本发明实施例提供了一种确定最大影响程度指标的种子集合的方法，该方法包括：
获取有向图，所述有向图包括：多个节点以及连接多个节点的多条有向边，每个节点表示网络环境中的一个用户，每条有向边对应一个激活概率；
根据预设的轮询参数，计算待生成子图的初始数量；
利用预设的竞争节点，以及有向图中随机选择的起始节点，生成初始数量个子图，子图中包括：被起始节点依次激活的多个目标节点以及多个目标节点之间的目标有向边，其中，最后一个被起始节点激活的目标节点为竞争节点，竞争节点为竞争者种子集合在有向图中的节点；
将获得的多个子图加入预设的集合，得到子图集合；
将有向图中的每个节点，分别单独加入预设的种子集合中，得到不同的第一种子集合；
计算每个第一种子集合在子图集合中的影响程度指标，确定影响程度指标最大的第一种子集合；
针对有向图中的当前节点，将每个当前节点分别单独加入影响程度指标最大的第一种子集合中，获得第二种子集合，直至第二种子集合中的节点个数与预设的种子用户的个数相同，当前节点为有向图中，除影响程度指标最大的第一种子集合中的节点以外的节点；
计算每个第二种子集合在子图集合中的影响程度指标；
将影响程度指标最大的第二种子集合，确定为目标种子集合。
可选的，利用预设的竞争节点，以及有向图中随机选择的起始节点，生成初始数量个子图的步骤，包括：
在有向图中随机选择起始节点，并确定依次被起始节点激活的目标节点，直至被激活的最后一个目标节点为竞争节点；
利用多个目标节点以及多个目标节点之间的目标有向边构造子图，直至所生成的子图数量达到初始数量。
可选的，将影响程度指标最大的第二种子集合，确定为目标种子集合的步骤之后，本发明第一方面实施例提供的一种确定最大影响程度指标的种子集合的方法还包括：
当目标种子集合的影响程度指标不大于影响程度指标阈值时，获取新的子图；
将新的子图加入子图集合中，直至子图集合中的子图个数达到第一子图数量阈值，第一子图数量阈值为子图数量的上限值；
确定子图个数达到第一子图数量阈值时的子图集合对应的种子集合，作为目标种子集合。
可选的，将影响程度指标最大的第二种子集合，确定为目标种子集合的步骤之后，本发明第一方面实施例提供的一种确定最大影响程度指标的种子集合的方法还包括：
计算目标种子集合的预期影响程度指标；
当目标种子集合的影响程度指标大于影响程度指标阈值时，设置初始目标值；
根据预设的竞争者种子集合，在有向图中随机选择起始节点，确定依次被起始节点激活的节点，获得目标子图；
将初始目标值与目标种子集合在目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标。
可选的，将初始目标值与目标种子集合在目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标的步骤之后，本发明第一方面实施例提供的一种确定最大影响程度指标的种子集合的方法还包括：
判断目标影响程度指标是否大于第二阈值，第二阈值表示子图影响程度指标下限值；
如果目标影响程度指标大于子图影响程度指标下限，则针对目标子图，计算目标种子集合的影响程度指标预测值；
判断目标种子集合的影响程度指标预测值是否大于目标种子集合的预期影响程度指标；
如果影响程度指标预测值大于目标种子集合的预期影响程度指标，则执行将新的子图加入子图集合中，直至子图集合中的子图个数达到第一子图数量阈值的步骤，第一子图数量阈值为子图数量的上限值；
将子图个数达到第一子图数量阈值时的子图集合对应的种子集合，作为目标种子集合。
可选的，判断目标影响程度指标是否大于第二阈值的步骤之后，本发明第一方面实施例提供的一种确定最大影响程度指标的种子集合的方法还包括：
如果目标影响程度指标不大于第二阈值，则重复执行根据预设的竞争者种子集合，在已获得的有向图中随机选择起始节点，确定依次被起始节点激活的节点，获得目标子图；将初始目标值与目标种子集合在多个目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标的步骤，直至目标影响程度指标大于第二阈值。
第二方面，本发明实施例提供的一种确定最大影响程度指标的种子集合的装置，该装置包括：
获取模块，用于获取有向图，有向图包括：多个节点以及连接多个节点的多条有向边，每个节点表示网络环境中的一个用户，每条有向边对应一个激活概率。
数量计算模块，用于根据预设的轮询参数，计算待生成子图的初始数量。
生成模块，用于利用预设的竞争节点，以及有向图中随机选择的起始节点，生成初始数量个子图，子图中包括：被起始节点依次激活的多个目标节点以及多个目标节点之间的目标有向边，其中，最后一个被起始节点激活的目标节点为竞争节点，竞争节点为竞争者种子集合在有向图中的节点.。
第一添加模块，用于将获得的多个子图加入预设的集合，得到子图集合。
第二添加模块，用于将有向图中的每个节点，分别单独加入预设的种子集合中，得到不同的第一种子集合。
第一确定模块，用于计算每个第一种子集合在子图集合中的影响程度指标，确定影响程度指标最大的第一种子集合。
第三添加模块，用于针对有向图中的当前节点，将每个当前节点分别单独加入影响程度指标最大的第一种子集合中，获得第二种子集合，直至第二种子集合中的节点个数与预设的种子用户的个数相同，当前节点为有向图中，除影响程度指标最大的第一种子集合中的节点以外的节点。
指标计算模块，用于计算每个第二种子集合在子图集合中的影响程度指标。
第二确定模块，用于将影响程度指标最大的第二种子集合，确定为目标种子集合。
可选的，生成模块包括：激活子模块以及构造子模块，
激活子模块，用于在有向图中随机选择起始节点，并确定依次被起始节点激活的目标节点，直至被激活的最后一个目标节点为竞争节点。
构造子模块，用于利用多个目标节点以及多个目标节点之间的目标有向边构造子图，直至所生成的子图数量达到初始数量。
可选的，本发明实施里提供的一种确定最大影响程度指标的种子集合的装置还包括：
种子集合更新模块，用于：
当目标种子集合的影响程度指标不大于影响程度指标阈值时，获取新的子图。
将新的子图加入子图集合中，直至子图集合中的子图个数达到第一子图数量阈值，第一子图数量阈值为子图数量的上限值。
确定子图个数达到第一子图数量阈值时的子图集合对应的种子集合，作为目标种子集合。
可选的，本发明实施里提供的一种确定最大影响程度指标的种子集合的装置还包括：
评价模块，用于：
计算目标种子集合的预期影响程度指标。
当目标种子集合的影响程度指标大于影响程度指标阈值时，设置初始目标值。
根据预设的竞争者种子集合，在有向图中随机选择起始节点，确定依次被起始节点激活的节点，获得目标子图。
将初始目标值与目标种子集合在目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标。
可选的，评价模块，用于：
判断目标影响程度指标是否大于第二阈值，第二阈值表示子图影响程度指标下限值。
如果目标影响程度指标大于子图影响程度指标下限，则针对目标子图，计算目标种子集合的影响程度指标预测值。
判断目标种子集合的影响程度指标预测值是否大于目标种子集合的预期影响程度指标。
如果影响程度指标预测值大于目标种子集合的预期影响程度指标，则执行将新的子图加入子图集合中，直至子图集合中的子图个数达到第一子图数量阈值的步骤，第一子图数量阈值为子图数量的上限值。
确定子图个数达到第一子图数量阈值时的子图集合对应的种子集合，作为目标种子集合的步骤。
可选的，评价模块，用于：
如果目标影响程度指标不大于第二阈值，则重复执行根据预设的竞争者种子集合，在已获得的有向图中随机选择起始节点，确定依次被起始节点激活的节点，获得目标子图；将初始目标值与目标种子集合在多个目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标的步骤，直至目标影响程度指标大于第二阈值。
第三方面，本发明实施例提供了一种服务器，包括处理器、通信接口、存储器和通信总线，其中，所述处理器、所述通信接口、所述存储器通过所述通信总线完成相互间的通信；所述机器可读存储介质存储有能够被所述处理器执行的机器可执行指令，所述处理器被所述机器可执行指令促使：实现本发明实施例第一方面提供的一种确定最大影响程度指标的种子集合的方法步骤。
第四方面，本发明实施例提供了一种计算机可读存储介质，所述计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行本发明实施例第一方面提供的一种确定最大影响程度指标的种子集合的方法步骤。
第五方面，本发明实施例还提供了一种包含指令的计算机程序产品，当其在计算机上运行时，使得计算机执行本发明实施例第一方面提供的一种确定最大影响程度指标的种子集合的方法步骤。
本发明实施例提供的一种确定最大影响程度指标的种子集合的方法及装置，获取有向图，根据预设的轮询参数，计算待生成子图的初始数量，利用预设的竞争节点，以及有向图中随机选择的起始节点，生成初始数量个子图，将获得的多个子图加入预设的集合，得到子图集合，将有向图中的每个节点，分别单独加入预设的种子集合中，获得不同的第一种子集合，计算每个第一种子集合在子图集合中的影响程度指标，确定影响程度指标最大的第一种子集合，针对有向图中的当前节点，将每个当前节点分别单独加入影响程度指标最大的第一种子集合中，获得第二种子集合，直至第二种子集合中的节点个数与预设的种子用户的个数相同，计算每个第二种子集合在子图集合中的影响程度指标，将影响程度指标最大的第二种子集合，确定为目标种子集合。本发明实施例通过计算待生成子图的初始数量，从有向图中获得与初始数量相同的子图，得到子图集合，针对有向图的当前节点，添加一次当前节点至种子集合，只需计算一次种子集合在子图集合中的影响程度指标，相比于现有技术，该过程无需模拟产品的传播过程，因此减少了确定对种子集合影响程度指标最大的节点的时间，然后选择对种子集合影响程度指标最大的节点添加至种子集合中，直至种子集合中种子的个数达到预设的种子用户个数，然后将该种子集合作为目标种子集合，因此能够减少确定目标种子集合的时间。当然，实施本发明的任一产品或方法并不一定需要同时达到以上的所有优点。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1为本发明实施例提供的有向图的示意图；
图2为本发明实施例提供的一种确定最大影响程度指标的种子集合的方法的流程图；
图3为本发明实施例提供实现s203的步骤过程的流程图；
图4为本发明实施例提供实现s2031的步骤过程的流程图；
图5为本发明实施例提供的有向图细节结构示意图；
图6为本发明实施例提供的在达到子图上限的子图集合中，确定目标种子集过程的流程图；
图7为本发明实施例提供的评估目标种子集影响程度指标过程的流程图；
图8为本发明实施例提供的评估目标种子集预期影响程度指标过程的流程图；
图9为本发明实施例提供的一种确定最大影响程度指标的种子集合的装置的结构示意图；
图10为本发明实施例提供的一种电子设备的结构示意图。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
如图2所示，本发明实施例提供了一种确定最大影响程度指标的种子集合的方法，该方法包括：
s201，获取有向图。
其中，有向图中包括：多个节点以及连接多个节点的多条有向边，每个节点表示网络环境中的一个用户，每条有向边对应一个激活概率。
可以理解，可以预先通过模拟网路环境以及用户之间的关系，构建给定网络，使用独立级联模型，将该给定网络抽象为一个有向图g，以此来获取有向图。
参考图1，有向图g中包含各个用户节点，记为v，例如1至12，以及用户节点与用户节点之间的有向边，记为e，每个有向边对应一个激活概率，一个用户节点沿着有向边的方向，服从该有向边对应的激活概率以激活另一个用户节点，例如：0至1之间的有向边可以表示为有向箭头。
s202，根据预设的轮询参数，计算待生成子图的初始数量。
其中，本发明实施例中的子图是在竞争节点存在的情况下，利用反向可达的原理，基于有向图中有向边的反方向，逆推出可以被初始节点激活的节点，从而得出的子图，该子图称为竞争反向可达子图，可以使用子图初始数量表达式，根据预设的轮询参数，计算待生成子图的初始数量，子图初始数量表达式为：
n＝h(∈1,∈2,∈3,δ)，
其中，
在实际运行时，∈＝0.1,
s203，利用预设的竞争节点，以及有向图中随机选择的起始节点，生成初始数量个子图。
其中，子图中包括：被起始节点依次激活的多个目标节点以及多个目标节点之间的目标有向边，其中，最后一个被起始节点激活的目标节点为竞争节点，预设的竞争节点是竞争者种子集合中的种子用户对应的有向图中的节点。
可以理解，选择起始节点的目的是，确定被起始节点激活的其他节点，进一步可以确定激活节点之间的有向边，才能构造一个子图，而随机选择起始节点可以降低重复选择同一个起始节点的概率，且随机选择方式耗费的时间较少，保证减少子图重复的现象同时提高生成子图的效率。而子图的初始数量通过预设的轮询参数，计算得出，在∈＝0.1,
作为本发明实施例提供的一种可选的实施方式，如图3所示，上述s203的步骤可以通过如下步骤实现：
s2031，在有向图中随机选择起始节点，并确定依次被起始节点激活的目标节点，直至被激活的最后一个目标节点为竞争节点。
可以理解，同一类型的两个产品进行竞争，其中一个可以为目标产品，另一个为竞争产品，竞争产品的种子用户抽象为有向图中的竞争节点，目标产品的种子用户抽象为有向图中的目标节点，与初始节点相邻的邻居节点最先被初始节点激活，当邻居节点被激活后就会激活与自己相邻的邻居节点，由于存在竞争节点，最后一个被激活的是竞争节点意味着竞争产品与目标产品存在同一个种子用户，这样会降低目标产品的宣传效果，因此当存在被激活的节点是竞争节点就停止激活节点的过程。
s2032，利用多个目标节点以及多个目标节点之间的目标有向边构造子图，直至所生成的子图数量达到初始数量。
可以理解，目标节点在有向图中预先都有节点编号，目标有向边在有向图中也有编号，根据目标节点在有向图中的连接关系以及目标有向边的位置，将各个目标节点与目标有向边的关系，就可以构造一个子图。重复生成子图的步骤，就可以生成初始数量个子图。
作为本发明实施例提供的一种可选的实施方式，如图4所示，上述s2031的步骤可以通过如下实现：
s2031a，利用预设的竞争节点，在有向图中随机选择起始节点，确定起始节点服从第1激活概率，激活的第1目标节点。
s2031b，设置初始值m为2，将m按单位整数递增的顺序，执行确定第m目标节点服从第m 1激活概率，激活的第m 1个目标节点直至被激活的最后一个目标节点为竞争节点。
相应的，上述s2032的步骤可以通过如下实现：
s2032a，在有向图中随机选择起始节点，确定出的所有目标节点以及所有目标节点之间的有向边构造一个子图。
s2032b，重复s2031a至s2032a的步骤，直至生成子图的数量达到初始数量。
示例性的，如图5所示，将社交网络建模为一个有向图g＝(v,e)，将社交网络中的用户建模为图g中的节点，v表示图g中的节点集合，将用户之间的影响关系建模为图g中的有向边，e表示图g中的有向边集合。对于e中任意一条有向边euv,使用puv∈[0,1]表示节点u对于节点v的影响强度，一个被激活的节点u∈v将会尝试激活它的所有邻居节点，对于邻居节点v的激活概率为puv，即有向边euv的激活概率为puv。
可以理解，假设有两个同一类型的产品竞争，分为为a产品和b产品，已经获知b产品的种子集合为sb，目标产品的目标种子集合为sa。考虑a、b两种产品信息同时在社交网络上传播，并且两者之间为竞争关系，即一位用户仅接受其中一种产品信息。因此，假设有向图中任意节点v只有三种可能状态：a1激活状态、b1激活状态和未激活状态，并且一旦节点转变为激活状态，将不能再改变其状态。其中a1(或b1)激活状态表示节点受到a(或b)产品信息的影响，未激活状态表示还未受到产品信息的影响。假设a、b两种产品信息的传播模型相同，即
接下来，介绍a产品和b产品两种产品，假设a产品为目标产品，需要为a产品宣传产品选择种子集合，下面介绍如何在sb存在的情况下，在有向图中选择起始节点，确定被起始节点激活的其他节点：
(1)判定有向图g中的每一条边是否为激活状态。以有向边euv为例，以puv的激活概率将其划分入集合ea，使ea包含图中所有判定为激活状态的有向边，ea与节点集合v组成了子图ga＝(v,ea)。
(2)定义
(3)对于图中节点u，若
最后，所有判定为a1激活状态的节点组成了受到a产品信息影响的节点集合va，同理可得受到b产品信息影响的节点集合vb。定义i(sa|sb)表示种子集合sa在图g中的影响程度指标，通常使用受到a产品信息影响的用户数量|va|作为其影响程度指标大小的评估方式，即i(sa|sb)＝|va|。
其中，符号的含义参见表1。
表1符号含义
示例性的，可以以下述过程确定子图：
(1)已知社交网络图g＝(v,e)和竞争者种子集合sb，在图g中随机选择一个节点r作为起始节点，构造子图
(2)遍历所有指向vr中新增节点的有向边，对于边euv，以puv的激活概率将其添加到er中。若成功将其添加到er中，则同时将其起点u加入vr中。
(3)若节点集合vr中有新增节点，检查新增节点中是否包含竞争者选取的种子。若
其中，
例如：参考图5，在有向图g中随机选择了节点v8作为起始节点，当v8激活v5、v6节点，则将节点v5、v6加入到子图集合vr中，v4没有被v8激活，则无需加入vr中，节点v2、v4被节点v5激活，v3被节点v6激活，则将节点v2、v3、v4加入到vr中，v9节点没有被激活，则无需加入到vr中。最后，由于节点v3为竞争节点，发现竞争节点停止此次采样。最终，本次采样生成了子图r＝(vr,er,sr,b)，其中vr＝{v2,v3,v4,v5,v6,v8}、er＝{e3,e4,e5,e7,e8}、sr,b＝{v2}。随机选择起始节点，生成子图，直至子图的数量达到初始数量n。
如图2所示，s204，将获得的多个子图加入预设的集合，得到子图集合。
基于上述解释，为了较为准确地估计种子集合sa在图g中的影响程度指标i(sa|sb)，需要通过竞争反向影响程度指标采样方法生成将n个子图r＝(vr,er,sr,b)加入子图集合
s205，将有向图中的每个节点，分别单独加入预设的种子集合中，得到不同的第一种子集合。
其中，预设的种子集合为空集。
示例性的，假设有向图中有4个节点，分别是a、b、c、d，将节点a、b、c、d分别加入预设的种子集合中，得到4个第一种子集合，分别是：{a}、{b}、{c}、{d}。
s206，计算每个第一种子集合在子图集合中的影响程度指标，确定影响程度指标最大的第一种子集合。
可以理解，已知竞争者的种子集合
因此，确定影响程度指标最大的第一种子集合，即需要筛选出当前阶段对于种子集合影响程度指标提升最大的节点，即
其中，种子集合影响程度指标表达式为：
fr(sa)表示在单个子图r中种子集合的影响程度指标，vt表示有向图中第t个节点，此处sa表示第一种子集合，ri表示子图集合中的第i个子图。
可以理解，当子图集合与第一种子集合没有相同节点时，第一种子集合的影响程度指标为0；当子图集合与第一种子集合具有相同节点，且竞争者的种子集与子图集合具有相同节点时，第一种子集合在单个子图r中影响程度指标为：
以图5中生成的子图r为例，已知竞争种子集合为：sr,b＝{v3}，若第一种子集合sa＝{v5}，则fr(sa)＝1；若sa＝{v2,v4}，由于dr(v2,v8)＝dr(v4,v8)＝dr(v3,v8)＝2，则
s207，针对有向图中的当前节点，将每个当前节点分别单独加入影响程度指标最大的第一种子集合中，获得第二种子集合，直至第二种子集合中的节点个数与预设的种子用户的个数相同。
其中，当前节点为有向图中，除影响程度指标最大的第一种子集合中的节点以外的节点。
作为本发明实施例提供的一种可选的实施方式，获得第二种子集合后，使用第二种子集合替换上述步骤s205中的第一种子集合，并重复执行s205至s207的步骤，直至第二种子集合中的节点个数与预设的种子用户的个数相同。
s208，计算每个第二种子集合在子图集合中的影响程度指标。
其中，可以使用种子集合影响程度指标表达式，计算每个第二种子集合在子图集合中的影响程度指标，种子集合影响程度指标表达式与上述计算每个第一种子集合影响程度指标的表达式相同，相应的，上述计算每个第一种子集合影响程度指标的表达式中sa在此处表示第二种子集合，计算过程此处不再赘述。
可以理解，当子图集合与第二种子集合没有相同节点时，第二种子集合的影响程度指标为0；当子图集合与第二种子集合具有相同节点，且竞争者的种子集与子图集合具有相同节点时，第二种子集合在单个子图r中影响程度指标为：
s209，将影响程度指标最大的第二种子集合，确定为目标种子集合。
示例性的，假设，有向图中包括的节点为：a、b、c、d，e，第一种子集合当分别是：{a}、{b}、{c}、{d}，{e}时，则需要计算第一种子集合{a}、第一种子集合{c}以及第一种子集合{e}的影响程度指标，然后选择影响程度指标最大的第一种子集合，假设影响程度指标最大的第一种子集合是{a}，则分别将剩余的节点b、c、d，e分别单独加入影响程度指标最大的第一种子集合是{a}中，获得第二种子集合{a，b}、{a，c}、{a，d}以及{a，e}，计算第二种子集合{a，b}、{a，c}、{a，d}以及第二种子集合{a，e}的在子图集合中的影响程度指标，假设{a，c}的影响程度指标最大，且预设的种子用户的个数为2时，则将种子集合{a，c}确定为目标种子集合。
本发明实施例通过计算待生成子图的初始数量，从有向图中获得与初始数量相同的子图，得到子图集合，针对有向图的当前节点，添加一次当前节点至种子集合，只需计算一次种子集合在子图集合中的影响程度指标，相比于现有技术，该过程无需模拟产品的传播过程，因此减少了确定对种子集合影响程度指标最大的节点的时间，然后选择对种子集合影响程度指标最大的节点添加至种子集合中，直至种子集合中种子的个数达到预设的种子用户个数，然后将该种子集合作为目标种子集合，因此能够减少确定目标种子集合的时间。
如图6所示，作为本发明实施例可选的一种实施方式，在上述s209的步骤之后，本发明实施例提供的一种确定最大影响程度指标的种子集合的方法还包括：
s601，当目标种子集合的影响程度指标不大于影响程度指标阈值时，获取新的子图。
可以理解，影响程度指标阈值是预先根据行业经验设置的数值，目标种子集合的影响程度指标已经在前述s208的实施例中得出，因此只需判断目标种子集合的影响程度指标是否大于影响程度指标阈值就可以。
s602，将新的子图加入子图集合中，直至子图集合中的子图个数达到第一子图数量阈值。
其中，第一子图数量阈值为子图数量的上限值，子图数量的上限值可以使用上限计算公式得到，上限计算公式为：
nmax表示子图数量的上限值，k为种子用户个数，n为网络图g中节点总数。
可以理解，基于独立级联模型的影响程度指标最大化问题无法在有限时间内求解出最优解。为了解决该问题，本发明实施例可以基于现有的(∈,δ)近似解框架，可以使得以大于(1-δ)的概率给出与最大影响程度指标的种子集合(最优解)的比值不小于(1-1/e-∈)的近似解。因此，将∈,δ计算满足精度要求近似解的子图数量的上限值，满足任意社交网络中均保证近似解满足精度要求，评估种子集合的影响程度指标是否满足要求，如果满足要求则算法提前结束并输出当前种子集合，如果没有满足要求则继续生成子图，直到子图数量达到nmax。若算法提前结束，则减少了子图生成数量，减少了算法求解时间；若子图数量达到nmax，此时种子集合的准确度提升。
s603，确定子图个数达到第一子图数量阈值时的子图集合对应的种子集合，作为目标种子集合。
如图7所示，作为本发明实施例可选的一种实施方式，在上述s209的步骤之后，本发明实施例提供的一种确定最大影响程度指标的种子集合的方法还包括：
s701，计算目标种子集合的预期影响程度指标。
上述可以使用预期影响程度表达式，计算目标种子集合的预期影响程度指标。其中，预期影响程度表达式为：
s702，当目标种子集合的影响程度指标大于影响程度指标阈值时，设置初始目标值。
s703，根据预设的竞争者种子集合，在有向图中随机选择起始节点，确定依次被起始节点激活的节点，获得目标子图。
s704，将初始目标值与目标种子集合在目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标。
其中，初始目标值是目标影响程度指标的初值，设置初始目标值f＝0，使用目标求和公式，求得目标影响程度指标。
其中，目标求和公式为：
结合图7，如图8所示，作为本发明实施例可选的一种实施方式，在上述s704的步骤之后，本发明实施例提供的一种确定最大影响程度指标的种子集合的方法还包括：
s801，判断目标影响程度指标是否大于第二阈值。
其中，第二阈值表示子图影响程度指标下限值，使用下限值表达式可以计算第二阈值，下限值表达式为：
s802，如果目标影响程度指标大于子图影响程度指标下限，则针对目标子图，计算目标种子集合的影响程度指标预测值。
其中，影响程度指标预测值可以通过预测表达式计算得到，预测表达式为:
其中，
s803，判断目标种子集合的影响程度指标预测值是否大于目标种子集合的预期影响程度指标。
s804，如果影响程度指标预测值大于目标种子集合的预期影响程度指标，则执行将新的子图加入子图集合中，直至子图集合中的子图个数达到第一子图数量阈值的步骤，第一子图数量阈值为子图数量的上限值。
s805，将子图个数达到第一子图数量阈值时的子图集合对应的种子集合，作为目标种子集合。
可以理解，为了可以正确评估目标种子集合sa的预期影响程度指标，根据子图集合
结合图7，如图8所示，作为本发明实施例可选的一种实施方式，在上述s801的步骤之后，本发明实施例提供的一种确定最大影响程度指标的种子集合的方法还包括：
如果目标影响程度指标不大于第二阈值，则重复执行根据预设的竞争者种子集合，在已获得的有向图中随机选择起始节点，确定依次被起始节点激活的节点，获得目标子图；将初始目标值与目标种子集合在多个目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标的步骤，直至目标影响程度指标大于第二阈值。
结合图7，如图8所示，作为本发明实施例可选的一种实施方式，在上述s803的步骤之后，本发明实施例提供的一种确定最大影响程度指标的种子集合的方法还包括：
如果目标种子集合的影响程度指标预测值不大于目标种子集合的预期影响程度指标，则重复执行根据预设的竞争者种子集合，在已获得的有向图中随机选择起始节点，确定依次被起始节点激活的节点，获得目标子图；将初始目标值与目标种子集合在多个目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标，判断目标影响程度指标是否大于第二阈值，判断目标影响程度指标是否大于第二阈值，第二阈值表示子图影响程度指标下限值；如果目标影响程度指标大于子图影响程度指标下限，则针对目标子图，计算目标种子集合的影响程度指标预测值，判断目标种子集合的影响程度指标预测值是否大于目标种子集合的预期影响程度指标的步骤，直至目标种子集合的影响程度指标预测值大于目标种子集合的预期影响程度指标。
如图9所示，本发明实施例提供的一种确定最大影响程度指标的种子集合的装置，该装置包括：
获取模块901，用于获取有向图，有向图包括：多个节点以及连接多个节点的多条有向边，每个节点表示网络环境中的一个用户，每条有向边对应一个激活概率。
数量计算模块902，用于根据预设的轮询参数，计算待生成子图的初始数量。
生成模块903，用于利用预设的竞争节点，以及有向图中随机选择的起始节点，生成初始数量个子图，子图中包括：被起始节点依次激活的多个目标节点以及多个目标节点之间的目标有向边，其中，最后一个被起始节点激活的目标节点为竞争节点，竞争节点为竞争者种子集合在有向图中的节点.。
第一添加模块904，用于将获得的多个子图加入预设的集合，得到子图集合。
第二添加模块905，用于将有向图中的每个节点，分别单独加入预设的种子集合中，得到不同的第一种子集合。
第一确定模块906，用于计算每个第一种子集合在子图集合中的影响程度指标，确定影响程度指标最大的第一种子集合。
第三添加模块907，用于针对有向图中的当前节点，将每个当前节点分别单独加入影响程度指标最大的第一种子集合中，获得第二种子集合，直至第二种子集合中的节点个数与预设的种子用户的个数相同，当前节点为有向图中，除影响程度指标最大的第一种子集合中的节点以外的节点。
指标计算模块908，用于计算每个第二种子集合在子图集合中的影响程度指标。
第二确定模块909，用于将影响程度指标最大的第二种子集合，确定为目标种子集合。
可选的，生成模块包括：激活子模块以及构造子模块，
激活子模块，用于在有向图中随机选择起始节点，并确定依次被起始节点激活的目标节点，直至被激活的最后一个目标节点为竞争节点。
构造子模块，用于利用多个目标节点以及多个目标节点之间的目标有向边构造子图，直至所生成的子图数量达到初始数量。
可选的，本发明实施里提供的一种确定最大影响程度指标的种子集合的装置还包括：
种子集合更新模块，用于：
当目标种子集合的影响程度指标不大于影响程度指标阈值时，获取新的子图。
将新的子图加入子图集合中，直至子图集合中的子图个数达到第一子图数量阈值，第一子图数量阈值为子图数量的上限值。
确定子图个数达到第一子图数量阈值时的子图集合对应的种子集合，作为目标种子集合。
可选的，本发明实施里提供的一种确定最大影响程度指标的种子集合的装置还包括：
评价模块，用于：
计算目标种子集合的预期影响程度指标。
当目标种子集合的影响程度指标大于影响程度指标阈值时，设置初始目标值。
根据预设的竞争者种子集合，在有向图中随机选择起始节点，确定依次被起始节点激活的节点，获得目标子图。
将初始目标值与目标种子集合在目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标。
可选的，评价模块，用于：
判断目标影响程度指标是否大于第二阈值，第二阈值表示子图影响程度指标下限值。
如果目标影响程度指标大于子图影响程度指标下限，则针对目标子图，计算目标种子集合的影响程度指标预测值。
判断目标种子集合的影响程度指标预测值是否大于目标种子集合的预期影响程度指标。
如果影响程度指标预测值大于目标种子集合的预期影响程度指标，则执行将新的子图加入子图集合中，直至子图集合中的子图个数达到第一子图数量阈值的步骤，第一子图数量阈值为子图数量的上限值。
确定子图个数达到第一子图数量阈值时的子图集合对应的种子集合，作为目标种子集合的步骤。
可选的，评价模块，用于：
如果目标影响程度指标不大于第二阈值，则重复执行根据预设的竞争者种子集合，在已获得的有向图中随机选择起始节点，确定依次被起始节点激活的节点，获得目标子图；将初始目标值与目标种子集合在多个目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标的步骤，直至目标影响程度指标大于第二阈值。
本发明实施例通过计算待生成子图的初始数量，从有向图中获得与初始数量相同的子图，得到子图集合，针对有向图的当前节点，添加一次当前节点至种子集合，只需计算一次种子集合在子图集合中的影响程度指标，相比于现有技术，该过程无需模拟产品的传播过程，因此减少了确定对种子集合影响程度指标最大的节点的时间，然后选择对种子集合影响程度指标最大的节点添加至种子集合中，直至种子集合中种子的个数达到预设的种子用户个数，然后将该种子集合作为目标种子集合，因此能够减少确定目标种子集合的时间。
本发明实施例还提供了一种电子设备，如图10所示，包括处理器1001、通信接口1002、存储器1003和通信总线1004，其中，处理器1001，通信接口1002，存储器1003通过通信总线1004完成相互间的通信，
存储器1003，用于存放计算机程序；
处理器1001，用于执行存储器1003上所存放的程序时，实现如下步骤：
获取有向图，所述有向图包括：多个节点以及连接所述多个节点的多条有向边，每个节点表示网络环境中的一个用户，每条有向边对应一个激活概率。
根据预设的轮询参数，计算待生成子图的初始数量。
利用预设的竞争节点，以及所述有向图中随机选择的起始节点，生成所述初始数量个子图，所述子图中包括：被所述起始节点依次激活的多个目标节点以及多个目标节点之间的目标有向边，其中，最后一个被所述起始节点激活的所述目标节点为竞争节点，所述竞争节点为竞争者种子集合在所述有向图中的节点。
将获得的多个子图加入预设的集合，得到子图集合。
将所述有向图中的每个节点，分别单独加入预设的种子集合中，得到不同的第一种子集合。
计算每个第一种子集合在所述子图集合中的影响程度指标，确定影响程度指标最大的第一种子集合。
针对所述有向图中的当前节点，将每个当前节点分别单独加入所述影响程度指标最大的第一种子集合中，获得第二种子集合，直至第二种子集合中的节点个数与预设的种子用户的个数相同，所述当前节点为所述有向图中，除所述影响程度指标最大的第一种子集合中的节点以外的节点。
计算每个第二种子集合在所述子图集合中的影响程度指标。
将所述影响程度指标最大的第二种子集合，确定为目标种子集合。
本发明实施例通过计算待生成子图的初始数量，从有向图中获得与初始数量相同的子图，得到子图集合，针对有向图的当前节点，添加一次当前节点至种子集合，只需计算一次种子集合在子图集合中的影响程度指标，相比于现有技术，该过程无需模拟产品的传播过程，因此减少了确定对种子集合影响程度指标最大的节点的时间，然后选择对种子集合影响程度指标最大的节点添加至种子集合中，直至种子集合中种子的个数达到预设的种子用户个数，然后将该种子集合作为目标种子集合，因此能够减少确定目标种子集合的时间。
上述电子设备提到的通信总线可以是外设部件互连标准(peripheralcomponentinterconnect，pci)总线或扩展工业标准结构(extendedindustrystandardarchitecture，eisa)总线等。该通信总线可以分为地址总线、数据总线、控制总线等。为便于表示，图中仅用一条粗线表示，但并不表示仅有一根总线或一种类型的总线。
通信接口用于上述电子设备与其他设备之间的通信。
存储器可以包括随机存取存储器(randomaccessmemory，ram)，也可以包括非易失性存储器(non-volatilememory，nvm)，例如至少一个磁盘存储器。可选的，存储器还可以是至少一个位于远离前述处理器的存储装置。
上述的处理器可以是通用处理器，包括中央处理器(centralprocessingunit，cpu)、网络处理器(networkprocessor，np)等；还可以是数字信号处理器(digitalsignalprocessing，dsp)、专用集成电路(applicationspecificintegratedcircuit，asic)、现场可编程门阵列(field-programmablegatearray，fpga)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件。
在本发明提供的又一实施例中，还提供了一种计算机可读存储介质，该计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时实现上述任一一种确定最大影响程度指标的种子集合的方法的步骤。
在本发明提供的又一实施例中，还提供了一种包含指令的计算机程序产品，当其在计算机上运行时，使得计算机执行上述实施例中任一一种确定最大影响程度指标的种子集合的方法。
在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。所述计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行所述计算机程序指令时，全部或部分地产生按照本发明实施例所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一个计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线(例如同轴电缆、光纤、数字用户线(dsl))或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。所述计算机可读存储介质可以是计算机能够存取的任何可用介质或者是包含一个或多个可用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质，(例如，软盘、硬盘、磁带)、光介质(例如，dvd)、或者半导体介质(例如固态硬盘solidstatedisk(ssd))等。
需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。
本说明书中的各个实施例均采用相关的方式描述，各个实施例之间相同相似的部分互相参见即可，每个实施例重点说明的都是与其他实施例的不同之处。尤其，对于装置实施例而言，由于其基本相似于方法实施例，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。
以上所述仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内所作的任何修改、等同替换、改进等，均包含在本发明的保护范围内。
1.一种确定最大影响程度指标的种子集合的方法，其特征在于，所述方法包括：
获取有向图，所述有向图包括：多个节点以及连接所述多个节点的多条有向边，每个节点表示网络环境中的一个用户，每条有向边对应一个激活概率；
根据预设的轮询参数，计算待生成子图的初始数量；
利用预设的竞争节点，以及所述有向图中随机选择的起始节点，生成所述初始数量个子图，所述子图中包括：被所述起始节点依次激活的多个目标节点以及多个目标节点之间的目标有向边，其中，最后一个被所述起始节点激活的所述目标节点为竞争节点，所述竞争节点为竞争者种子集合在所述有向图中的节点；
将获得的多个子图加入预设的集合，得到子图集合；
将所述有向图中的每个节点，分别单独加入预设的种子集合中，得到不同的第一种子集合；
计算每个所述第一种子集合在所述子图集合中的影响程度指标，确定影响程度指标最大的第一种子集合；
针对所述有向图中的当前节点，将每个当前节点分别单独加入所述影响程度指标最大的第一种子集合中，获得第二种子集合，直至第二种子集合中的节点个数与预设的种子用户的个数相同，所述当前节点为所述有向图中，除所述影响程度指标最大的第一种子集合中的节点以外的节点；
计算每个所述第二种子集合在所述子图集合中的影响程度指标；
将影响程度指标最大的第二种子集合，确定为目标种子集合。
2.根据权利要求1所述的方法，其特征在于，所述利用预设的竞争节点，以及所述有向图中随机选择的起始节点，生成所述初始数量个子图的步骤，包括：
在所述有向图中随机选择起始节点，并确定依次被所述起始节点激活的目标节点，直至被激活的最后一个目标节点为所述竞争节点；
利用所述多个目标节点以及多个目标节点之间的目标有向边构造所述子图，直至所生成的子图数量达到所述初始数量。
3.根据权利要求1所述的方法，其特征在于，所述将所述影响程度指标最大的第二种子集合，确定为目标种子集合的步骤之后，所述方法还包括：
当所述目标种子集合的影响程度指标不大于影响程度指标阈值时，获取新的子图；
将所述新的子图加入所述子图集合中，直至所述子图集合中的子图个数达到第一子图数量阈值，所述第一子图数量阈值为子图数量的上限值；
确定子图个数达到第一子图数量阈值时的所述子图集合对应的种子集合，作为所述目标种子集合。
4.根据权利要求3所述的方法，其特征在于，所述将所述影响程度指标最大的第二种子集合，确定为目标种子集合的步骤之后，所述方法还包括：
计算所述目标种子集合的预期影响程度指标；
当所述目标种子集合的影响程度指标大于影响程度指标阈值时，设置初始目标值；
根据预设的竞争者种子集合，在所述有向图中随机选择起始节点，确定依次被起始节点激活的节点，获得目标子图；
将所述初始目标值与所述目标种子集合在所述目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标。
5.根据权利要求4所述的方法，其特征在于，所述将所述初始目标值与目标种子集合在所述目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标的步骤之后，所述方法还包括：
判断所述目标影响程度指标是否大于第二阈值，所述第二阈值表示所述子图影响程度指标下限值；
如果所述目标影响程度指标大于子所述图影响程度指标下限，则针对所述目标子图，计算所述目标种子集合的影响程度指标预测值；
判断所述目标种子集合的影响程度指标预测值是否大于所述目标种子集合的预期影响程度指标；
如果所述影响程度指标预测值大于所述目标种子集合的预期影响程度指标，则执行所述将所述新的子图加入所述子图集合中，直至所述子图集合中的子图个数达到第一子图数量阈值的步骤，所述第一子图数量阈值为子图数量的上限值；
将子图个数达到第一子图数量阈值时的所述子图集合对应的种子集合，作为所述目标种子集合。
6.根据权利要求5所述的方法，其特征在于，所述判断所述目标影响程度指标是否大于第二阈值的步骤之后，所述方法还包括：
如果所述目标影响程度指标不大于所述第二阈值，则重复执行所述根据预设的竞争者种子集合，在所述已获得的有向图中随机选择起始节点，确定依次被起始节点激活的节点，获得目标子图；将初始目标值与所述目标种子集合在所述多个目标子图中的影响程度指标求和，将求和结果作为目标影响程度指标的步骤，直至所述目标影响程度指标大于第二阈值。
7.一种确定最大影响程度指标的种子集合的装置，其特征在于，所述装置包括：
获取模块，用于获取有向图，所述有向图包括：多个节点以及连接所述多个节点的多条有向边，每个节点表示网络环境中的一个用户，每条有向边对应一个激活概率；
数量计算模块，用于根据预设的轮询参数，计算待生成子图的初始数量；
生成模块，用于利用预设的竞争节点，以及所述有向图中随机选择的起始节点，生成所述初始数量个子图，所述子图中包括：被所述起始节点依次激活的多个目标节点以及多个目标节点之间的目标有向边，其中，最后一个被所述起始节点激活的所述目标节点为竞争节点，所述竞争节点为竞争者种子集合在所述有向图中的节点；
第一添加模块，用于将获得的多个子图加入预设的集合，得到子图集合；
第二添加模块，用于将所述有向图中的每个节点，分别单独加入预设的种子集合中，得到不同的第一种子集合；
第一确定模块，用于计算每个所述第一种子集合在所述子图集合中的影响程度指标，确定影响程度指标最大的第一种子集合；
第三添加模块，用于针对所述有向图中的当前节点，将每个当前节点分别单独加入所述影响程度指标最大的第一种子集合中，获得第二种子集合，直至第二种子集合中的节点个数与预设的种子用户的个数相同，所述当前节点为所述有向图中，除所述影响程度指标最大的第一种子集合中的节点以外的节点；
指标计算模块，用于计算每个所述第二种子集合在所述子图集合中的影响程度指标；
第二确定模块，用于将所述影响程度指标最大的第二种子集合，确定为目标种子集合。
8.根据权利要求7所述的装置，其特征在于，所述生成模块包括：
激活子模块，用于在所述有向图中随机选择起始节点，并确定依次被所述起始节点激活的目标节点，直至被激活的最后一个目标节点为所述竞争节点；
构造子模块，用于利用所述多个目标节点以及多个目标节点之间的目标有向边构造所述子图，直至所生成的子图数量达到所述初始数量。
9.一种电子设备，其特征在于，包括处理器、通信接口、存储器和通信总线，其中，处理器，通信接口，存储器通过通信总线完成相互间的通信；
存储器，用于存放计算机程序；
处理器，用于执行存储器上所存放的程序时，实现权利要求1-6任一所述的方法步骤。
10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时实现权利要求1-6任一所述的方法步骤。
技术总结