(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111550263.6 (22)申请日 2021.12.17 (71)申请人 东北大学 地址 110819 辽宁省沈阳市和平区文化路3 号巷11号 (72)发明人 马连博　王博涵　何强　王兴伟　 黄敏　 (74)专利代理 机构 沈阳东大知识产权代理有限 公司 21109 代理人 李在川 (51)Int.Cl. G06F 30/27(2020.01) G06Q 50/00(2012.01) G06F 119/02(2020.01) (54)发明名称 基于机器学习构建的社交网络影响最大化 确定方法 (57)摘要 本发明提供一种基于机器学习构建的社交 网络影响最大化确定方法， 属于社交网络影响最 大化技术领域； 首先获取社交网络数据集并对社 交网络数据集进行预处理， 然后创建基于独立联 级传播模型的最大化求解模型， 包括多搜索模式 粒子群， 学习自动机和局部搜索机； 最后给定一 个社交网络数据集， 利用构建的求解模型对这个 社交网络的种子集进行求解； 粒子群的应用实现 了问题求解的智 能性， 降低了问题的复杂度； 学 习自动机的引入实现了粒子群的多搜索模式， 解 决了对于解集空间探索失衡且模式单一的问题； 局部搜索机用于探索邻居解， 有效加速了优化算 法的收敛速度。 权利要求书3页 说明书10页 附图5页 CN 114239403 A 2022.03.25 CN 114239403 A 1.一种基于 机器学习构建的社交网络影响最大化确定方法， 其特 征在于， 包括： 步骤1： 获取 社交网络数据集并对数据集进行 预处理； 步骤2： 根据多搜索模式粒子群、 学习自动机和 局部搜索机构建影响最大化 求解模型； 步骤3： 根据社交网络数据集通过影响最大化求解模型输出能在网络中取得最大传播 影响力的一组用户。 2.根据权利要求1所述的一种基于机器学习构建的社交网络影响最大化确定方法， 其 特征在于， 所述 步骤1包括： 步骤1.1： 将数据集中所有节点个体进行编号， 根据节点间的链接计算每个节点的入 度； 步骤1.2： 根据节点的入度信息以及节点的链接方向生成边信息， 所述边信息包括： 传 播节点、 被激活节点、 传播 概率。 3.根据权利要求1所述的一种基于机器学习构建的社交网络影响最大化确定方法， 其 特征在于， 所述步骤2中所述多搜索 模式粒子群用于对粒子群的速度向量进行更新； 所述学 习自动机用于对最优更新方式进行选择， 并对概率集进行更新； 所述局部搜索机用于对完 成一次迭代后的粒子群进行最优种子集的搜索。 4.根据权利要求3所述的一种基于机器学习构建的社交网络影响最大化确定方法， 其 特征在于， 所述步骤2中所述学习自动机为固定结构学习自动机， 并行使用奖励与惩罚机 制。 5.根据权利要求4所述的一种基于机器学习构建的社交网络影响最大化确定方法， 其 特征在于， 所述 步骤2包括： 步骤2.1： 创建三种粒子 速度向量更新方式作为粒子的不同搜索模式； 步骤2.2： 为每 个粒子分配一个自动学习机来确定在每 轮更新中所采用的搜索模式； 步骤2.3： 在每 个粒子更新完成后调用局部 搜索机进一 步搜索粒子的最优位置向量。 6.根据权利要求1所述的一种基于机器学习构建的社交网络影响最大化确定方法， 其 特征在于， 所述 步骤3包括： 步骤3.1： 初始化种群， 每个粒子的属性包括： 位置向量、 位置向量适应度值、 速度向量、 学习自动机概率集、 局部最优解Pbest以及Pbest的适应度值； 其中， 位置向量以节 点的度为 参考并结合随即策略生成， 为k个不重复的节点编号； 位置向量适应度值根据适应度值函数 计算获得； 速度向量初始化为零向量， 维度与位置向量相同； 学习自动机概率集对应三种粒 子群更新方式， 初始化 为1/3； 局部最优解初始化 为当前位置向量； 步骤3.2： 初始化全局最优位置向量集Gbest， 在种群中的粒子中选取位置向量适应度 值最大的三个粒子的位置向量， 由大到小分别赋值于向量Gbest1、 Gbest 2与Gbest3； 步骤3.3： 对种群的粒子逐个迭代， 根据概率集选取粒子群更新方式生成粒子的新速度 向量， 根据速度向量在原位置 向量的基础上通过变异获得新位置 向量， 并记录更新的向量 维度， 利用适应度函数对新 位置向量进行评估得到新 位置向量的适应度值； 步骤3.4： 根据粒子新位置向量对Gbest与粒子的Pbest进行更新， 适应度 值小的位置向 量由适应度值大的位置向量取代； 步骤3.5： 对粒子的学习自动机概率集进行更新， 若新位置向量更新为Pbest则使用奖 励机制对学习自动机概率集进行更新， 若新位置向量未能更新Pbest则使用惩罚机制 对学权　利　要　求　书 1/3 页 2 CN 114239403 A 2习自动机概 率集进行更新； 步骤3.6： 应用局部搜索进一步搜索最优位置向量， 根据步骤3.3中记录的更新的向量 维度， 将这些维度上 的节点用其原本节点的邻居节点代替获得一组位置 向量， 然后用这组 位置向量对Gbest进行 更新； 步骤3.7： 当达到迭代次数后停止迭代， 将向量Gbest1中k个维度所对应的节点作为求 解的大小为k的种子集， 应用蒙特卡罗模拟获得种子集真实的传播影响力； 输出的种子集即 为影响力最大的一组用户数据。 7.根据权利要求6所述的一种基于机器学习构建的社交网络影响最大化确定方法， 其 特征在于， 所述步骤3.1中的适应度值函数为两跳影响扩散模拟方法， 用于近似模拟种子集 的真实传播影响力。 8.根据权利要求6所述的一种基于机器学习构建的社交网络影响最大化确定方法， 其 特征在于， 所述步骤3.3中的粒子速度向量更新过程包括通过经典粒子群对粒子速度向量 进行更新、 通过全局粒子群对粒子速度向量进行更新、 通过精英粒子群对粒子速度向量进 行更新， 粒子通过 学习自动机 选择每一轮的更新方式； 所述经典粒子群对粒子 速度向量进行 更新， 包括： 步骤1‑1： 将原速度向量乘以惯性系数 得到向量 list1； 步骤1‑2： 将粒子的位置向量与向量Gbest1进行比较， 若某维度上的节点不存在于 Gbest1中， 则向量 list2对应维度记为1， 否则记为0； 步骤1‑3： 将粒子的位置向量与粒子的Pbest进行比较， 若某维度上的节点不存在于 Pbest中， 则向量 list3对应维度记为1， 否则记为0； 步骤1‑4： 将向量list2和向量list3分别乘以范围在0到2的随机数后与向量list1合 并， 以2为分割数归一 化处理得到新速度向量。 9.根据权利要求8所述的一种基于机器学习构建的社交网络影响最大化确定方法， 其 特征在于， 所述 通过全局粒子群对粒子 速度向量进行 更新， 包括： 步骤2‑1： 将原速度向量乘以惯性系数 得到向量 list1； 步骤2‑2： 将粒子位置向量的每一维度与通过锦标赛策略选出k个参考粒子的位置向量 进行比较， 若 该维度上的节点不存在于参考粒子的位置向量中， 则向量list2对应维度 记为 1， 否则记为0； 步骤2‑3： 将向量list2乘以范围在0到4的随机数后与向量list1合并， 以2为分割数归 一化处理得到新速度向量。 10.根据权利要求8所述的一种基于机器学习构建的社交网络影响最大化确定方法， 其 特征在于， 所述 通过精英粒子群对粒子 速度向量进行 更新， 包括： 步骤3‑1： 将原速度向量乘以惯性系数 得到向量 list1； 步骤3‑2： 将粒子的位置向量与Gbest 1的位置向量进行比较， 若某 维度上的节点不存在 于向量Gbest1中， 则向量 list2对应维度记为1， 否则记为0； 步骤3‑3： 将粒子的位置向量与Gbest2的位置向量进行比较， 若某 维度上的节点不存在 于向量Gbest 2中， 则向量 list3对应维度记为1， 否则记为0； 步骤3‑4： 将粒子的位置向量与Gbest3的位置向量进行比较， 若某 维度上的节点不存在 于向量Gbest3中， 则向量 list4对应维度记为1， 否则记为0；权　利　要　求　书 2/3 页 3 CN 114239403 A 3