基于超图和普通图混合求解最大影响力种子节点的方法

1.本发明涉及计算机应用领域，尤其是一种基于超图和普通图混合求解最大影响力种子节点的方法。


背景技术：

2.现有的研究证明了社交网络中有些用户能够具有更大的影响力，且只有少数有影响力的人可以在信息传播过程中塑造和改变大多数人的意见。因此，识别社交网络中有影响力的用户或者网络中有影响力的节点，通常可以辅助解决许多不同类型的问题，而确定最具影响力的传播者可以用来达到最大的传播能力。复杂网络中有影响力的节点具有最大的传播能力。因此，节点的中心性与其影响最大化(im)之间存在高度相关性。
3.但现有研究主要集中在网络的二元关系上，缺乏对实体间高阶关系的考虑，对于实际问题的建模不足以解决部分复杂问题，当交互作用涉及两个以上实体时，具有二元关系的普通网络中的边缘很难描述交互作用。在im问题上，要么考虑将超图转换为普通二部图，要么通过贪心算法来处理超图中的im问题。目前超图中的im问题仍然存在以下问题：一是在效率与最优结果中的平衡，超图的高阶结构导致其在求解最优解时往往需要花费大量时间，因此目前的大部分算法均很难适用于大规模的超图网络。二是如何评估超图结构下的节点拓展影响力，目前并无相关指标被设计来解决此问题。三是已经提出的算法如何从普通网络拓展到超图。


技术实现要素：

4.有鉴于此，本发明提供一种基于超图和普通图混合求解最大影响力种子节点的方法，以从超图和普通图的混合网络结构中求解最大影响力种子节点。
5.本发明的一方面提供了一种基于超图和普通图混合求解最大影响力种子节点的方法，包括：
6.在超图和普通图中获取影响力最大的前k个节点，作为候选节点，k为正整数；
7.对k个所述候选节点执行初始化算子，以生成初始种群，所述初始种群包括多个个体，每个所述个体对应多个所述候选节点；
8.对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点；
9.根据各个所述个体对应的候选节点的影响力，更新所述个体对应的候选节点；
10.根据各个所述候选节点的影响力从多个所述个体中选出多个目标个体组成新的种群；
11.将所述新的种群作为新的所述初始种群，执行所述对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点的步骤，直至满足设定的终止条件；
12.输出最终得到的种群，并根据迭代次数从所述最终得到的种群中确定节点影响力
最大的最优个体，所述最优个体对应的候选节点作为种子节点。
13.可选地，所述对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点，包括：
14.随机选择两个进行交叉操作的个体，并在进行交叉操作的两个个体中分别随机选择一个交叉点，在该交叉点对选择的两个个体进行节点序列交叉互换；
15.随机选择进行变异操作的个体，生成一个新的节点并替换进行变异操作的个体对应的候选节点。
16.可选地，所述根据各个所述个体对应的候选节点的影响力，更新所述个体对应的候选节点，包括：
17.根据第一预设概率确定全局搜索个体，将所述全局搜索个体中的其中一个搜索节点与一个随机节点进行影响力比较，若所述随机节点的影响力大于所述搜索节点的影响力，则将所述搜索节点替换为所述随机节点，所述随机节点为所述超图和普通图中的任意一个节点；
18.根据第二预设概率确定局部搜索个体，对所述局部搜索个体遍历搜索每个候选节点的2-hop邻域内的局部邻域，对所述局部邻域内的所有候选节点计算出影响力，并根据影响力更新所述局部邻域内的候选节点。
19.可选地，所述根据各个所述候选节点的影响力从多个所述个体中选出多个目标个体组成新的种群，包括：
20.利用轮盘赌选择从多个所述个体中选出候选节点的影响力达到预设值的多个目标个体，以组成新的种群。
21.可选地，所述方法还包括：
22.将候选节点的影响力小于所述预设值的个体加入到所述新的种群中。
23.可选地，根据预设的影响力评估表达式计算得到超图中种子节点的影响力；
24.所述预设的影响力评估表达式为：
[0025][0026]
其中，σ(s)表示超图中种子节点的影响力，hg1是距离k＝1的超图，hg2是距离k＝2的超图，p(s,c)是激活节点s到非激活节点c的激活概率，表示超图hg1中激活节点s所在的超边中的节点数，表示超图hg2中激活节点s所在的超边的节点数，表示hg1中激活节点s所处的超边中所有节点的集合，表示hg2中激活节点s所处的超边中所有节点的集合。
[0027]
可选地，所述根据迭代次数从所述最终得到的种群中确定节点影响力最大的最优个体，包括：
[0028]
确定所述超图和所述普通图的混合比、预设的最大迭代次数以及最终迭代次数；
[0029]
若所述最终迭代次数小于所述混合比与所述预设的最大迭代次数的乘积，则根据所述预设的影响力评估表达式从所述最终得到的种群中确定节点影响力最大的最优个体；
[0030]
若所述最终迭代次数大于所述混合比与所述预设的最大迭代次数的乘积，则根据所述普通图对应的影响力评估表达式从所述最终得到的种群中确定节点影响力最大的最优个体。
[0031]
本发明的另一方面还提供了一种基于超图和普通图混合求解最大影响力种子节点的装置，包括：
[0032]
第一单元，用于在超图和普通图中获取影响力最大的前k个节点，作为候选节点，k为正整数；
[0033]
第二单元，用于对k个所述候选节点执行初始化算子，以生成初始种群，所述初始种群包括多个个体，每个所述个体对应多个所述候选节点；
[0034]
第三单元，用于对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点；
[0035]
第四单元，用于根据各个所述个体对应的候选节点的影响力，更新所述个体对应的候选节点；
[0036]
第五单元，用于根据各个所述候选节点的影响力从多个所述个体中选出多个目标个体组成新的种群；
[0037]
第六单元，用于将所述新的种群作为新的所述初始种群，执行所述对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点的步骤，直至满足设定的终止条件；
[0038]
第七单元，用于输出最终得到的种群，并根据迭代次数从所述最终得到的种群中确定节点影响力最大的最优个体，所述最优个体对应的候选节点作为种子节点。
[0039]
本发明的另一方面还提供了一种电子设备，包括处理器以及存储器；
[0040]
所述存储器用于存储程序；
[0041]
所述处理器执行所述程序实现所述的方法。
[0042]
本发明的另一方面还提供了一种计算机可读存储介质，所述存储介质存储有程序，所述程序被处理器执行实现所述的方法。
[0043]
本发明还公开了一种计算机程序产品或计算机程序，该计算机程序产品或计算机程序包括计算机指令，该计算机指令存储在计算机可读存储介质中。电子设备的处理器可以从计算机可读存储介质读取该计算机指令，处理器执行该计算机指令，使得该电子设备执行上述的方法。
[0044]
本发明提出了一种混合超图和普通图的网络影响力最大化解决方法，利用本发明可以综合使用超图的影响力求解指标与普通图的影响力求解指标，以防止陷入局部最优化的困境。而且，相较于现有技术，本发明具有收敛速度快、不易陷入局部最优解、解的质量优于其他现有技术、高效率和高质量等优点。
附图说明
[0045]
为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0046]
图1为本发明实施例提供的一种基于超图和普通图混合求解最大影响力种子节点的方法的流程示意图；
[0047]
图2为本发明实施例提供的一种求解种子节点最大影响力的示例流程图；
[0048]
图3为本发明实施例提供的一种基于超图和普通图混合求解最大影响力种子节点的装置的结构框图。
具体实施方式
[0049]
为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
[0050]
需要说明的是，虽然在装置示意图中进行了功能模块划分，在流程图中示出了逻辑顺序，但是在某些情况下，可以以不同于装置中的模块划分，或流程图中的顺序执行所示出或描述的步骤。
[0051]
说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。
[0052]
除非另有定义，本文所使用的所有的技术和科学术语与属于本发明的技术领域的技术人员通常理解的含义相同。本文中所使用的术语只是为了描述本发明实施例的目的，不是旨在限制本发明。
[0053]
参照图1，本发明实施例提供了一种基于超图和普通图混合求解最大影响力种子节点的方法，具体如下：
[0054]
s100：在超图和普通图中获取影响力最大的前k个节点，作为候选节点，k为正整数。
[0055]
具体地，本发明实施例的普通图是指二部图。首先，进行初始化操作，根据节点的影响力大小选出k个候选节点，形成候选集。带有偏好的初始化操作可以提高候选解的质量，加速收敛至最优解。可选地，选取候选节点的概率与候选节点影响力大小成正比。
[0056]
s110：对k个所述候选节点执行初始化算子，以生成初始种群，所述初始种群包括多个个体，每个所述个体对应多个所述候选节点。
[0057]
具体地，对k个所述候选节点执行初始化算子以生成初始种群，用于后续的遗传进化操作。
[0058]
s120：对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点。
[0059]
作为进一步可选的实施方式，s120可以包括：
[0060]
s121：随机选择两个进行交叉操作的个体，并在进行交叉操作的两个个体中分别随机选择一个交叉点，在该交叉点对选择的两个个体进行节点序列交叉互换。
[0061]
具体地，进行交叉操作，每个种群成员(即个体)都有可能进行交叉操作。在选择进
行交叉的两个个体时，随机选定一个交叉点，并将交叉位置后的基因片段互换。如果交叉后的个体中存在重复节点，则需随机生成一个新基因用于交换重复节点，以确保个体之间没有重复节点。其中，交叉点是进行交叉操作的节点位置，交叉位置是进行交叉操作的两个个体对应的节点位置，基因片段是个体的节点序列。
[0062]
s122：随机选择进行变异操作的个体，生成一个新的节点并替换进行变异操作的个体对应的候选节点。
[0063]
具体地，进行变异操作，每个个体在一定概率下执行变异算子，向种群引入新的候选节点，以避免陷入局部最优。被选中的个体将随机选择一个其自身对应的候选节点并用新生成的不与该个体中已有节点重复的节点进行替换，也即每个个体以一定概率执行变异算子，执行变异算子的个体随机选择一个节点，该节点将被替换为随机选择的网络中的其他不与现有节点重复的节点。
[0064]
s130：根据各个所述个体对应的候选节点的影响力，更新所述个体对应的候选节点。
[0065]
作为进一步可选的实施方式，130可以包括：
[0066]
s131：根据第一预设概率确定全局搜索个体，将所述全局搜索个体中的其中一个搜索节点与一个随机节点进行影响力比较，若所述随机节点的影响力大于所述搜索节点的影响力，则将所述搜索节点替换为所述随机节点，所述随机节点为所述超图和普通图中的任意一个节点。
[0067]
具体地，进行全局搜索操作，对于每个个体，以一定概率执行全局搜索算子。选中的个体将从全局网络中随机选择一个节点与其某个节点进行比较。如果新节点的影响力大于该节点，则接受新节点并更新。否则不接受更新，并继续在下一个节点上执行全局搜索操作。
[0068]
s132：根据第二预设概率确定局部搜索个体，对所述局部搜索个体遍历搜索每个候选节点的2-hop邻域内的局部邻域，对所述局部邻域内的所有候选节点计算出影响力，并根据影响力更新所述局部邻域内的候选节点。
[0069]
具体地，进行局部搜索操作，对于每个个体，以一定概率执行局部搜索算子。被选中的个体将遍历搜索每个节点的2-hop邻域内的局部邻域。然后，为每个节点执行替换操作，根据随机数的结果，计算超图影响力指标或普通图影响力指标并选择性能最优的个体来更新。
[0070]
s140：根据各个所述候选节点的影响力从多个所述个体中选出多个目标个体组成新的种群。
[0071]
作为进一步可选的实施方式，s140可以包括：
[0072]
利用轮盘赌选择从多个所述个体中选出候选节点的影响力达到预设值的多个目标个体，以组成新的种群。
[0073]
更进一步地，s140还可以包括：
[0074]
将候选节点的影响力小于所述预设值的个体加入到所述新的种群中。
[0075]
具体地，进行选择操作，根据适应度值(节点影响力)的概率选取个体，并利用轮盘赌选择将适应度值较大的个体选择进入下一代种群。适应度较小的个体同样可以有被选择的机会，以提升种群的多样性。最优的个体直接进入下一代以确保种群不会退化。
[0076]
然后，将所述新的种群作为新的所述初始种群，重复执行步骤120至步骤140，直至满足设定的终止条件，再执行步骤s150。其中，设定的终止条件可以包括达到预设的迭代次数或满足预设的其他要求。
[0077]
s150：输出最终得到的种群，并根据迭代次数从所述最终得到的种群中确定节点影响力最大的最优个体，所述最优个体对应的候选节点作为种子节点。
[0078]
本发明实施例还提供一种评估超图节点影响力的方法，具体如下：
[0079]
根据预设的影响力评估表达式计算得到超图中种子节点的影响力；
[0080]
所述预设的影响力评估表达式为：
[0081][0082]
其中，σ(s)表示超图中种子节点的影响力，hg1是距离k＝1的超图，hg2是距离k＝2的超图，p(s,c)是激活节点s到非激活节点c的激活概率，表示超图hg1中激活节点s所在的超边中的节点数，表示超图hg2中激活节点s所在的超边的节点数，表示hg1中激活节点s所处的超边中所有节点的集合，表示hg2中激活节点s所处的超边中所有节点的集合。
[0083]
进一步地，步骤s150中的所述根据迭代次数从所述最终得到的种群中确定节点影响力最大的最优个体，可以包括：
[0084]
确定所述超图和所述普通图的混合比、预设的最大迭代次数以及最终迭代次数；
[0085]
若所述最终迭代次数小于所述混合比与所述预设的最大迭代次数的乘积，则根据所述预设的影响力评估表达式从所述最终得到的种群中确定节点影响力最大的最优个体；
[0086]
若所述最终迭代次数大于所述混合比与所述预设的最大迭代次数的乘积，则根据所述普通图对应的影响力评估表达式从所述最终得到的种群中确定节点影响力最大的最优个体。
[0087]
可选地，上述根据所述普通图对应的影响力评估表达式从所述最终得到的种群中确定节点影响力最大的最优个体的步骤，可以利用现有技术完成。
[0088]
接下来，将以具体实例说明本发明的应用过程。
[0089]
本发明实施例提供了一种基于超图和普通图混合求解最大影响力种子节点的方法，并提供了一种基于超图的影响力的评估方法，并与现有的普通图影响力评估方法结合，得到一种性能更优的影响力最大化的方法。
[0090]
(1)基于超图节点影响力评估指标：
[0091][0092]
由上式可知，为了得到超图结构下的二邻域影响力大小，需要分别构建一个距离k
＝1的超图hg1与距离k＝2的超图hg2。其中，p(s,c)时激活节点s到非激活节点c的激活概率，表示超图hg1中激活节点s所在的超边中的节点数，表示超图hg2中激活节点s所在的超边的节点数，表示hg1中激活节点s所处的超边中的所有节点集，表示hg2中激活节点s所处的超边种的所有节点集。在上式中，第一项和第二项定义了种子的2-hop邻域范围，而后第三项和第四项分别扣除了种子节点邻域和2-hop邻域中与种子节点集合中重复的节点数。
[0093]
(2)超图影响力与普通图影响力的混合方法：
[0094]
g《ps(hg,g)*maxgen
[0095]
ps(hg,g)代表着超图和普通图之间的混合比，g为迭代数，maxgen为预设的最大迭代次数。当迭代数g小于ps(hg,g)*maxgen时，则使用上述基于超图节点影响力评估指标选取种子集合，当g大于ps(hg,g)*maxgen时，则使用普通图的影响力评估方法选取种子集合。可选地，使用普通图的影响力评估方法选取种子集合的步骤可以由现有技术实现。
[0096]
(3)参照图2，本发明实施例提供了一种求解种子节点最大影响力的示例流程图，本发明实施例可以将超图的节点影响力评估指标与普通图节点影响力的评估方法结合，用于求解种子节点最大影响力问题，步骤包括如下：
[0097]
(3a)执行初始化算子，初始化种群；
[0098]
(3b)评估个体适应度：根据预定义的适应度函数，对每个个体进行评价，并给出一个适应度(最大影响力)得分；
[0099]
(3c)对种群执行交叉算子，交换个体间基因片段；
[0100]
(3d)根据随机数判断本局该使用基于超图的影响力评估指标还是基于普通图的影响力评估指标；
[0101]
(3e)选择优秀个体：采用轮盘赌选择法或其他选择策略，从种群中选择适应度高的个体，并将其作为下一代种群的“父母”；
[0102]
(3f)进行交叉和变异操作：采用交叉和变异技术，通过修改父母的基因序列来产生新的个体；
[0103]
(3g)更新种群：将新的个体加入到种群中，同时淘汰适应度较低的个体，保持种群规模不变；
[0104]
(3h)判断停止条件：如果达到预设的最大迭代次数，或者符合其他停止条件，则停止算法，输出种群中适应度最高的个体作为最终结果；
[0105]
(3i)输出结果：将适应度最高的个体转换成实际的文化模因，输出给用户或保存到数据库中。
[0106]
本发明与现有技术相比具备以下有益效果：
[0107]
首先，本发明提出了超图的影响力评价指标，为超图结构下求解最大影响力种子节点提供了方法和依据，而现有方法大多是基于普通图的影响力求解，关于超图的影响力最大化求解较少，通过本发明可以较好的解决超图的影响力最大化问题。
[0108]
其次，本发明提出了一种基于超图和普通图混合求解最大影响力种子节点的方法，利用该方法可以综合使用超图的影响力求解指标与普通二部图的影响力求解指标，以防止陷入局部最优化的困境。
[0109]
最后，相较于现有的方法，本发明提出的方法具有收敛速度快、不易陷入局部最优
解、解的质量优于其他方法、高效率和高质量等优点。
[0110]
参照图3，本发明实施例提供了一种基于超图和普通图混合求解最大影响力种子节点的装置，包括：
[0111]
第一单元，用于在超图和普通图中获取影响力最大的前k个节点，作为候选节点，k为正整数；
[0112]
第二单元，用于对k个所述候选节点执行初始化算子，以生成初始种群，所述初始种群包括多个个体，每个所述个体对应多个所述候选节点；
[0113]
第三单元，用于对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点；
[0114]
第四单元，用于根据各个所述个体对应的候选节点的影响力，更新所述个体对应的候选节点；
[0115]
第五单元，用于根据各个所述候选节点的影响力从多个所述个体中选出多个目标个体组成新的种群；
[0116]
第六单元，用于将所述新的种群作为新的所述初始种群，执行所述对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点的步骤，直至满足设定的终止条件；
[0117]
第七单元，用于输出最终得到的种群，并根据迭代次数从所述最终得到的种群中确定节点影响力最大的最优个体，所述最优个体对应的候选节点作为种子节点。
[0118]
上述装置的具体实施方式与上述方法的具体实施例基本相同，在此不再赘述。
[0119]
本发明实施例还提供了一种计算机可读存储介质，该计算机可读存储介质存储有计算机程序，该计算机程序被处理器执行时实现上述方法。
[0120]
存储器作为一种非暂态计算机可读存储介质，可用于存储非暂态软件程序以及非暂态性计算机可执行程序。此外，存储器可以包括高速随机存取存储器，还可以包括非暂态存储器，例如至少一个磁盘存储器件、闪存器件、或其他非暂态固态存储器件。在一些实施方式中，存储器可选包括相对于处理器远程设置的存储器，这些远程存储器可以通过网络连接至该处理器。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。
[0121]
本发明实施例还公开了一种计算机程序产品或计算机程序，该计算机程序产品或计算机程序包括计算机指令，该计算机指令存储在计算机可读存储介质中。电子设备的处理器可以从计算机可读存储介质读取该计算机指令，处理器执行该计算机指令，使得该电子设备执行图1所示的方法。
[0122]
在一些可选择的实施例中，在方框图中提到的功能/操作可以不按照操作示图提到的顺序发生。例如，取决于所涉及的功能/操作，连续示出的两个方框实际上可以被大体上同时地执行或所述方框有时能以相反顺序被执行。此外，在本发明的流程图中所呈现和描述的实施例以示例的方式被提供，目的在于提供对技术更全面的理解。所公开的方法不限于本文所呈现的操作和逻辑流程。可选择的实施例是可预期的，其中各种操作的顺序被改变以及其中被描述为较大操作的一部分的子操作被独立地执行。
[0123]
此外，虽然在功能性模块的背景下描述了本发明，但应当理解的是，除非另有相反说明，所述的功能和/或特征中的一个或多个可以被集成在单个物理装置和/或软件模块
中，或者一个或多个功能和/或特征可以在单独的物理装置或软件模块中被实现。还可以理解的是，有关每个模块的实际实现的详细讨论对于理解本发明是不必要的。更确切地说，考虑到在本文中公开的装置中各种功能模块的属性、功能和内部关系的情况下，在工程师的常规技术内将会了解该模块的实际实现。因此，本领域技术人员运用普通技术就能够在无需过度试验的情况下实现在权利要求书中所阐明的本发明。还可以理解的是，所公开的特定概念仅仅是说明性的，并不意在限制本发明的范围，本发明的范围由所附权利要求书及其等同方案的全部范围来决定。
[0124]
所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台电子设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：u盘、移动硬盘、只读存储器(rom，read-only memory)、随机存取存储器(ram，random access memory)、磁碟或者光盘等各种可以存储程序代码的介质。
[0125]
在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令执行系统、装置或设备(如基于计算机的系统、包括处理器的系统或其他可以从指令执行系统、装置或设备取指令并执行指令的系统)使用，或结合这些指令执行系统、装置或设备而使用。就本说明书而言，“计算机可读介质”可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装置。
[0126]
计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布线的电连接部(电子装置)、便携式计算机盘盒(磁装置)、随机存取存储器(ram)、只读存储器(rom)、可擦除可编辑只读存储器(eprom或闪速存储器)、光纤装置以及便携式光盘只读存储器(cdrom)。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理来以电子方式获得所述程序，然后将其存储在计算机存储器中。
[0127]
应当理解，本发明的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门电路的离散逻辑电路，具有合适的组合逻辑门电路的专用集成电路，可编程门阵列(pga)，现场可编程门阵列(fpga)等。
[0128]
在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。
[0129]
尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不
脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同物限定。
[0130]
以上是对本发明的较佳实施进行了具体说明，但本发明并不限于所述实施例，熟悉本领域的技术人员在不违背本发明精神的前提下还可做出种种的等同变形或替换，这些等同的变形或替换均包含在本发明权利要求所限定的范围内。

技术特征：
1.一种基于超图和普通图混合求解最大影响力种子节点的方法，其特征在于，包括：在超图和普通图中获取影响力最大的前k个节点，作为候选节点，k为正整数；对k个所述候选节点执行初始化算子，以生成初始种群，所述初始种群包括多个个体，每个所述个体对应多个所述候选节点；对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点；根据各个所述个体对应的候选节点的影响力，更新所述个体对应的候选节点；根据各个所述候选节点的影响力从多个所述个体中选出多个目标个体组成新的种群；将所述新的种群作为新的所述初始种群，执行所述对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点的步骤，直至满足设定的终止条件；输出最终得到的种群，并根据迭代次数从所述最终得到的种群中确定节点影响力最大的最优个体，所述最优个体对应的候选节点作为种子节点。2.根据权利要求1所述的一种基于超图和普通图混合求解最大影响力种子节点的方法，其特征在于，所述对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点，包括：随机选择两个进行交叉操作的个体，并在进行交叉操作的两个个体中分别随机选择一个交叉点，在该交叉点对选择的两个个体进行节点序列交叉互换；随机选择进行变异操作的个体，生成一个新的节点并替换进行变异操作的个体对应的候选节点。3.根据权利要求1所述的一种基于超图和普通图混合求解最大影响力种子节点的方法，其特征在于，所述根据各个所述个体对应的候选节点的影响力，更新所述个体对应的候选节点，包括：根据第一预设概率确定全局搜索个体，将所述全局搜索个体中的其中一个搜索节点与一个随机节点进行影响力比较，若所述随机节点的影响力大于所述搜索节点的影响力，则将所述搜索节点替换为所述随机节点，所述随机节点为所述超图和普通图中的任意一个节点；根据第二预设概率确定局部搜索个体，对所述局部搜索个体遍历搜索每个候选节点的2-hop邻域内的局部邻域，对所述局部邻域内的所有候选节点计算出影响力，并根据影响力更新所述局部邻域内的候选节点。4.根据权利要求1所述的一种基于超图和普通图混合求解最大影响力种子节点的方法，其特征在于，所述根据各个所述候选节点的影响力从多个所述个体中选出多个目标个体组成新的种群，包括：利用轮盘赌选择从多个所述个体中选出候选节点的影响力达到预设值的多个目标个体，以组成新的种群。5.根据权利要求4所述的一种基于超图和普通图混合求解最大影响力种子节点的方法，其特征在于，所述方法还包括：将候选节点的影响力小于所述预设值的个体加入到所述新的种群中。6.根据权利要求1至5任一项所述的一种基于超图和普通图混合求解最大影响力种子节点的方法，其特征在于，根据预设的影响力评估表达式计算得到超图中种子节点的影响
力；所述预设的影响力评估表达式为：其中，σ(s)表示超图中种子节点的影响力，hg1是距离k＝1的超图，hg2是距离k＝2的超图，p(s,c)是激活节点s到非激活节点c的激活概率，表示超图hg1中激活节点s所在的超边中的节点数，表示超图hg2中激活节点s所在的超边的节点数，表示hg1中激活节点s所处的超边中所有节点的集合，表示hg2中激活节点s所处的超边中所有节点的集合。7.根据权利要求6所述的一种基于超图和普通图混合求解最大影响力种子节点的方法，其特征在于，所述根据迭代次数从所述最终得到的种群中确定节点影响力最大的最优个体，包括：确定所述超图和所述普通图的混合比、预设的最大迭代次数以及最终迭代次数；若所述最终迭代次数小于所述混合比与所述预设的最大迭代次数的乘积，则根据所述预设的影响力评估表达式从所述最终得到的种群中确定节点影响力最大的最优个体；若所述最终迭代次数大于所述混合比与所述预设的最大迭代次数的乘积，则根据所述普通图对应的影响力评估表达式从所述最终得到的种群中确定节点影响力最大的最优个体。8.一种基于超图和普通图混合求解最大影响力种子节点的装置，其特征在于，包括：第一单元，用于在超图和普通图中获取影响力最大的前k个节点，作为候选节点，k为正整数；第二单元，用于对k个所述候选节点执行初始化算子，以生成初始种群，所述初始种群包括多个个体，每个所述个体对应多个所述候选节点；第三单元，用于对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点；第四单元，用于根据各个所述个体对应的候选节点的影响力，更新所述个体对应的候选节点；第五单元，用于根据各个所述候选节点的影响力从多个所述个体中选出多个目标个体组成新的种群；第六单元，用于将所述新的种群作为新的所述初始种群，执行所述对所述初始种群中的各个个体进行交叉操作和变异操作，以更新所述个体对应的候选节点的步骤，直至满足设定的终止条件；第七单元，用于输出最终得到的种群，并根据迭代次数从所述最终得到的种群中确定节点影响力最大的最优个体，所述最优个体对应的候选节点作为种子节点。9.一种电子设备，其特征在于，包括处理器以及存储器；所述存储器用于存储程序；
所述处理器执行所述程序实现如权利要求1至7中任一项所述的方法。10.一种计算机可读存储介质，其特征在于，所述存储介质存储有程序，所述程序被处理器执行实现如权利要求1至7中任一项所述的方法。

技术总结
本发明公开了一种基于超图和普通图混合求解最大影响力种子节点的方法，该方法提供了一种基于超图的影响力的评估方法，并与现有的普通二部图影响力评估方法结合，得到一种性能更优的影响力最大化的方法。通过本发明可以从超图和普通图的混合网络结构中求解最大影响力种子节点，可广泛应用于计算机应用领域。可广泛应用于计算机应用领域。可广泛应用于计算机应用领域。


技术研发人员：王帅 何诗韵 关贝贝 雷箬儿 黎洁
受保护的技术使用者：中山大学
技术研发日：2023.07.21
技术公布日：2023/10/19