公开(公告)号：CN110135593A

公开(公告)日：2019-08-16

申请号：CN201910422268.7

申请日：2019-05-21

Applicant: 山东省计算中心(国家超级计算济南中心) ,  中国民航大学

Inventor： 赵大伟 ,  汪洁 ,  徐习鹏 ,  朱闻达 ,  武文敏 ,  江雨杭 ,  秦勉 ,  王连海

IPC: G06N99/00 ,  G06F17/50

Abstract: 本发明的多层网络最小支配集构造方法，通过以下步骤来实现：a).初始化支配集合D为空集；将相连的节点i与j的关联概率初始化为区间（0,1]内的随机值；b).构建信念传播方程，计算每个节点处于已被占据状态的概率；c).节点添加，将节点按照被占据状态概率值降序排列，将前r比例的节点添加到支配集中；d).连边和节点的删除；e).掐叶算法处理；f).再次迭代；g).直到获得一个有效的支配集D。本发明的多层网络最小支配集构造方法，通过构建的信念传播方程计算多层网络节点属于多层网络最小支配集的边际概率，并使用多层网络掐叶算法以降低计算复杂程度，可快速构造出大规模多层网络的近似最小支配集。