一种基于多层潜力和社区结构的影响最大化方法

摘要

本发明涉及一种基于多层潜力和社区结构的影响最大化方法，方法假设影响力的传播分为两个阶段，第一阶段：社区间基于多层潜力的种子扩算；第二阶段：社区内的影响传播；在第一阶段，种子节点v尝试激活其处于未激活状态的邻居节点{u|u∈N(v),active(u)＝0}，此过程中被激活的节点记为S₁，则有其中N(S)＝∪_v∈SN(v)，接下来，S₁又会尝试激活其处于未激活状态邻居节点{u|u∈N(S₁)/S,active(u)＝0}，此过程中被激活的节点记为S₂；在第二阶段，将节点影响的范围限制在其所在的社区中，对任意的社区该社区最终产生的影响规模取决于两个因素：1)社区C_i的大小|C_i|，2)S₂的节点落在该社区的个数|S₂∩C_i|。本发明提出的基于多层潜力和社区结构的影响最大化方法，其效率不仅比已有最新的算法(如IPA算法)高，而且其准确性也高于IPA算法及其他启发式算法。

主权项

一种基于多层潜力和社区结构的影响最大化方法，其特征在于：包括两个阶段，第一阶段：社区间基于多层潜力的种子扩算；第二阶段：社区内的影响传播；在第一阶段，种子节点v尝试激活其处于未激活状态的邻居节点{u|u∈N(v),active(u)＝0}，此过程中被激活的节点记为S₁，则有其中N(S)＝∪_v∈SN(v)，接下来，S₁又会尝试激活其处于未激活状态邻居节点{u|u∈N(S₁)/S,active(u)＝0}，此过程中被激活的节点记为S₂；在第二阶段，将节点影响的范围限制在其所在的社区中，对任意的社区影响规模取决于两个因素：1)社区C_i的大小|C_i|，2)S₂的节点落在该社区的个数|S₂∩C_i|，当|C_i|和|S₂∩C_i|越大时，该社区的影响范围就越大；当|C_i|＞＞|S₂∩C_i|时，该社区的影响取决于|S₂∩C_i|的值；当|C_i|≈|S₂∩C_i|时，该社区的影响取决于|C_i|的值。