·1264· 智能系统学报 第14卷 1.3影响力函数 6)对ps和C进行多项式拟合，求得拟合 定义影响力函数为(x):将有限集合映射到非 函数Fx): 负整数域上的函数。在网络中使用独立级联模型 7)求F(x)的导函数dFx); 模拟影响力传播的过程当中，种子集合S为初始 8)通过函数dFx)求得相变值p: 时刻已经激活的节点集合，在影响力传播过程的 9)最优种子集合大小K=P.×n 每个离散时刻都会因集合S激活一些未激活的节 本文提出一种基于渗流模型的影响力最大化 点，在影响力传播过程结束时我们可以得到在此 种子节点集合大小选取算法。算法的输入为：无 过程中激活的节点集合Aoal,即集合Aoal是被种 向网络G的上三角邻接矩阵G',传播概率数组 子节点集合S影响的节点集合。我们令种子节点 Ps,网络中节点的数量n,矩阵C和模拟次数R 集合S的影响力为(S,其值为4oal,即种子节点 因为本文主要研究无向网络，在对网络进行渗流 集合S的影响力是在影响力传播过程中被集合 模拟时，为了保持边的一致性，所以使用网络 S影响到的节点的个数。 G的上三角邻接矩阵G'。Pm是大小为1×1000的 一维数组，其中数组元素为0.001~1的数字，且相 2算法思想与步骤 邻元素相差0.001。C是大小为100×1000的矩 本文主要研究影响力最大化问题中种子节点 阵。因为在网络G上进行渗流的结果具有随机 集合大小选取的问题。在之前的研究中，研究人 性，所以我们在传播概率p∈Pm的情况下进行 员一般选取5~50个节点作为种子节点，并观察算 R次渗流。算法的输出为最优种子节点集合大小 法选取出的种子节点集合的影响力，旨在通过改 K。具体的算法步骤描述如下： 进算法得到更优的种子节点集合。而本文从网络 I)函数Ien(x)用来计算数组的长度，所以 传播影响力的固有能力的角度出发，发现网络在 len(p)的值等于1000，此步骤具体是：在传播概 选取种子节点时，并非越多越好，而是一定数量 率p∈pa的情况下，对网络G进行渗流； 的种子节点就能达到最优的影响力，即在网络中 2)采用当前传播概率p对网络G'进行R次 存在一个最优大小的种子节点集合，即我们所说 渗流； 的网络传播影响力的固有能力。为了研究网络传 3)渗流模型的定义如下：在网络G中，网络 播影响力的固有能力，本文借助渗流模型对网络 每条边具有统一的传播概率值P。我们对每条边 进行模拟分析，提出一种基于渗流模型的影响力 产生独立的随机值P,如果P,p,那么此边处于占 最大化算法，即在不同的传播概率p下对网络进 有状态，如果P,>P,那么此边处于非占有状态，也 行渗流模拟，通过建立传播概率p与渗流模拟后 就是此边从网络中删除。通过改变统一的传播概 网络的最大连通子图大小的函数关系，最终求得 率值p,那么存在一个值pe,当p>p时，GP中的节 当前网络所适合的种子节点集合的大小。具体算 点倾向于紧密的连接在一起，形成一个主团块。 法步骤如下： 当p<p。时，GP中的节点倾向于形成多个零散的 算法基于渗流模型的影响力最大化种子节 小团块。P.便称为网络G的相变值。图1为渗流 点集合大小选取算法 实验例图，图1(a)为2维晶格网络，网络中边的概 输入上三角邻接矩阵G',传播概率数组 率统一为p。图1(b)到图1(d)为渗流模拟后的网 P,网络中节点的数量n,矩阵C,模拟次数R 络，并且边的概率逐渐提高，我们发现当边的概 输出最优种子节点集合大小 率较低时，渗流模拟后的网络倾向于形成零散的 1)For i=1:1:len(pis) 团块，当边的概率较大时，渗流模拟后的网络倾 2)Forj=1:1:R 向于形成一个主团块，其存在一个过度值，即网 3) 根据Pt()对G'进行渗流模拟，形成 络由零散的团块到形成一个主团块的值，即相变 渗流后网络GP,并且获得GP的最大连通 值。图1(d)为2维品格网络发生渗流时的状态， 子图GP': 相变值P=0.6。在3)中，通过对网络G'进行渗流 4) C(U,）=num(GP: 模拟，可以得到渗流后的网络GP并且计算求得 End GP的最大连通子图GP: End 4)函数num(x)用于计算网络中节点的个数， 5)C=avg(C); 所以此步骤是将G的节点个数存入到C中；1.3 影响力函数 定义影响力函数为 I(x)：将有限集合映射到非 负整数域上的函数。在网络中使用独立级联模型 模拟影响力传播的过程当中，种子集合 S 为初始 时刻已经激活的节点集合，在影响力传播过程的 每个离散时刻都会因集合 S 激活一些未激活的节 点，在影响力传播过程结束时我们可以得到在此 过程中激活的节点集合 Atotal，即集合 Atotal 是被种 子节点集合 S 影响的节点集合。我们令种子节点 集合 S 的影响力为 I(S)，其值为|Atotal|，即种子节点 集合 S 的影响力是在影响力传播过程中被集合 S 影响到的节点的个数。 2 算法思想与步骤 本文主要研究影响力最大化问题中种子节点 集合大小选取的问题。在之前的研究中，研究人 员一般选取 5~50 个节点作为种子节点，并观察算 法选取出的种子节点集合的影响力，旨在通过改 进算法得到更优的种子节点集合。而本文从网络 传播影响力的固有能力的角度出发，发现网络在 选取种子节点时，并非越多越好，而是一定数量 的种子节点就能达到最优的影响力，即在网络中 存在一个最优大小的种子节点集合，即我们所说 的网络传播影响力的固有能力。为了研究网络传 播影响力的固有能力，本文借助渗流模型对网络 进行模拟分析，提出一种基于渗流模型的影响力 最大化算法，即在不同的传播概率 p 下对网络进 行渗流模拟，通过建立传播概率 p 与渗流模拟后 网络的最大连通子图大小的函数关系，最终求得 当前网络所适合的种子节点集合的大小。具体算 法步骤如下： 算法 基于渗流模型的影响力最大化种子节 点集合大小选取算法 输入 上三角邻接矩阵 G'，传播概率数组 plist，网络中节点的数量 n，矩阵 C，模拟次数 R; 输出 最优种子节点集合大小 k' 1) For i=1:1:len(plist) 2) For j=1:1: R 3) 根据 plist (i) 对 G'进行渗流模拟，形成 渗流后网络 GP，并且获得 GP 的最大连通 子图 GP'； 4) C(j,i)=num(GP')； End End 5) C'=avg(C)； 6) 对 plist 和 C 进行多项式拟合，求得拟合 函数 F(x)； 7) 求 F(x) 的导函数 dF(x)； 8) 通过函数 dF(x) 求得相变值 pc； k ′ 9) 最优种子集合大小 = pc ×n 1×1 000 100×1 000 p ∈ plist 本文提出一种基于渗流模型的影响力最大化 种子节点集合大小选取算法。算法的输入为：无 向网络 G 的上三角邻接矩阵 G'，传播概率数组 plist，网络中节点的数量 n，矩阵 C 和模拟次数 R。 因为本文主要研究无向网络，在对网络进行渗流 模拟时，为了保持边的一致性，所以使用网络 G 的上三角邻接矩阵 G'。plist 是大小为 的 一维数组，其中数组元素为 0.001~1 的数字，且相 邻元素相差 0.001。C 是大小为 的矩 阵。因为在网络 G 上进行渗流的结果具有随机 性，所以我们在传播概率 的情况下进行 R 次渗流。算法的输出为最优种子节点集合大小 k'。具体的算法步骤描述如下： p ∈ plist 1) 函数 len(x) 用来计算数组的长度，所以 len(plist) 的值等于 1 000，此步骤具体是：在传播概 率 的情况下，对网络 G'进行渗流； 2) 采用当前传播概率 p 对网络 G'进行 R 次 渗流； 3) 渗流模型的定义如下：在网络 G'中，网络 每条边具有统一的传播概率值 p。我们对每条边 产生独立的随机值 pr，如果 pr<p，那么此边处于占 有状态，如果 pr>p，那么此边处于非占有状态，也 就是此边从网络中删除。通过改变统一的传播概 率值 p，那么存在一个值 pc，当 p>pc时，GP 中的节 点倾向于紧密的连接在一起，形成一个主团块。 当 p<pc 时，GP 中的节点倾向于形成多个零散的 小团块。pc 便称为网络 G'的相变值。图 1 为渗流 实验例图，图 1(a) 为 2 维晶格网络，网络中边的概 率统一为 p。图 1(b) 到图 1(d)为渗流模拟后的网 络，并且边的概率逐渐提高，我们发现当边的概 率较低时，渗流模拟后的网络倾向于形成零散的 团块，当边的概率较大时，渗流模拟后的网络倾 向于形成一个主团块，其存在一个过度值，即网 络由零散的团块到形成一个主团块的值，即相变 值。图 1(d) 为 2 维晶格网络发生渗流时的状态， 相变值 pc=0.6。在 3) 中，通过对网络 G'进行渗流 模拟，可以得到渗流后的网络 GP 并且计算求得 GP 的最大连通子图 GP'； 4) 函数 num(x) 用于计算网络中节点的个数， 所以此步骤是将 GP'的节点个数存入到 C 中； ·1264· 智 能 系 统 学 报 第 14 卷