一种基于社区结构的影响最大化方法

专利类型：发明专利

语言：中文

申请号：CN201610340219.5

申请日：20160520

发明人：尚家兴武红春周尚波林晓然齐颖吴晓雨

申请人：重庆大学

申请人地址：400044 重庆市沙坪坝区沙坪坝正街174号

公开日：20160831

公开号：CN105913287A

代理人：赵荣之

代理机构：北京同恒源知识产权代理有限公司 11275

摘　　要：本发明提出一种基于社区结构的影响最大化方法。影响最大化问题研究如何从网络中找到k个种子节点作为初始传播源，使传播的最终影响范围最广。该问题是一个NP难题，传统的贪心算法效率很低，而简单的启发式算法得不到高质量的解。为解决上述问题，本发明提出了基于社区结构的影响最大化模型。模型假设传播分为两个阶段：第一阶段是种子节点的扩张，在该阶段种子节点可以扩张到各个社区；第二阶段是社区内传播，即扩张后的种子节点在各个社区内部独立传播。基于该模型推导出目标函数的一种简化形式，并提出一个高效的种子选取算法。在五个真实数据集上的实验结果表明，本发明所提算法效率远高于传统的贪心算法，且准确性高于简单的启发式算法。

主权项：一种基于社区结构的影响最大化方法，其特征在于：该方法包括以下步骤：S1：针对影响最大化问题，基于社区结构建立两阶段传播模型：第一阶段为传播初期不同社区间种子节点的扩张；第二阶段为社区内部的独立传播，即不同社区间不再相互传播；在该模型中，将种子节点集合S称为一阶种子节点，其邻居节点集合N(S)称为二阶种子节点，所述第一阶段就是从一阶种子节点到二阶种子节点的传播，第二阶段则是从二阶种子节点到社区内部其他节点的传播；在所述第一阶段中，传播主要从一阶种子节点S向二阶种子节点N(S)进行；由于二阶种子节点可能分布于不同的社区，因此这一阶段相当于把种子在不同的社区间进行扩散；给定一阶种子节点S，对任意一个二阶种子节点v∈N(S)，在经过第一阶段的传播之后，该节点处于活跃状态的概率是： $P_{v} (S) = 1 - \underset{u \in N (v) \cap S}{Π} (1 - p_{u v})$ 其中，p_uv是节点u到节点v的传播概率；在所述第二阶段中，传播只在社区内部进行，而不同社区间不会进行传播且每个社区内的传播行为相互独立；最终某个社区C内被影响的节点数取决于：社区包含的节点集合、一阶种子节点和二阶种子节点；因此，将其定义为一个函数f(S,S',C)，其中S和S'分别为一阶和二阶种子节点；整个网络的影响范围为： $f (S) = \underset{C \in C}{Σ} f (S, S^{'}, C);$ S2：根据步骤S1的结果将基于社区结构的影响最大化问题转化为：给定一个带非重叠社区结构C的网络G(V,E)以及相应的传播模型，寻找一个大小为k的种子节点集合S^*，使得公式中的影响函数f(S)最大化，即：S^*＝arg_Smaxf(S)。

关键词：

法律状态：公开

IPC专利分类号：G06Q30/02(2012.01)I