第14卷第6期 智能系统学报 Vol.14 No.6 2019年11月 CAAI Transactions on Intelligent Systems Nov.2019 D0:10.11992/tis.201906039 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20190722.1416.004.html 基于渗流模型的影响力最大化算法 花勇，陈伯伦，朱国畅，袁燕，金鹰 (淮阴工学院计算机与软件工程学院，江苏淮安223003) 摘要：多数社交网络影响力最大化算法的研究只关注于所选种子节点集合的影响力是否最优，忽略网络自身 传播影响力的固有能力。本文对网络进行渗流模拟，计算渗流后网络的主连通分量随着传播概率改变的趋势， 并且求得主连通分量大小增加开始变快的相变点，从而计算网络自身传播影响力的固有能力。通过相变值与 种子节点集合大小的换算，求得当前网络最佳的种子节点集合大小。将种子节点集合大小限制在最佳大小范 围内即可获得最佳的影响力。在kareteclub、football、highschool和socdolphins社交网络数据集上进行实验，验 证了该方法的有效性。 关键词：社交网络；影响力最大化：种子节点集合；渗流；传播概率；主连通分量；相变点；相变值 中图分类号：TP301.6文献标志码：A文章编号：1673-4785(2019)06-1262-09 中文引用格式：花勇，陈伯伦，朱国畅，等.基于渗流模型的影响力最大化算法.智能系统学报，2019,14(6)：1262-1270. 英文引用格式：HUA Yong,CHEN Bolun,.ZHU Guochang,etal.An influence maximization algorithm based on percolation model[J.CAAI transactions on intelligent systems,2019,14(6):1262-1270. An influence maximization algorithm based on percolation model HUA Yong,CHEN Bolun,ZHU Guochang,YUAN Yan,JIN Yin (School of Computer and Software Engineering,Huaiyin Institute of Technology,Huaian 223003,China) Abstract:Most of the influence maximization algorithms in social networks only focus on whether the influence of the seed node set selected is the optimal,and ignore the inherent ability of social network's propagating influence.Using percolation simulation,we calculate the change trend of the giant component of the network generation after percolation with propagation probability,and derive the starting point at which the size of the giant component increases fastest,that is,the phase point.The phase value shows the inherent ability of the network propagating influence.The optimal seed set size of the network can be calculated through conversion of the phase value and the size of the seed set.We can ob- tain the optimal influence by limiting the size of the seed set to the optimal size.We performed experiments on karate club,football,high school,and soc-dolphins,verifying the effectiveness of the algorithm. Keywords:social network;influence maximization;seed set,percolation;propagation probability;giant component; phase point;phase value 随着社交网络中信息量的快速增长，信息传 最大化问题是影响力分析的重要课题之一。2015 播速度的不断加快，其信息传播构建了一种分布 年，Morone和Makse在Nature上对社交网络中影 式传播机制山以及节点的合作机制)，即信息在 响力最大化问题进行了深入探讨。影响力最大 用户之间的扩散会受到用户影响力的影响。因 化问题解决的是如何衡量网络中节点重要性的问 此，开展影响力分析研究显得十分重要。影响力 题，其经典应用之一是病毒营销5)，也就是通过 口口相传效应进行产品的销售0。 收稿日期：2019-06-21.网络出版日期：2019-07-23 影响力最大化问题最早由Kempe等u率先 基金项目：国家自然科学基金项目(61602202)：江苏省自然科 学基金项目(BK20160428). 提出。Kempe等使用独立级联模型与线性阈值模 通信作者：陈伯伦.E-mail:chenbolunl986@163.com 型对社交网络中影响力的传播进行建模，并且证
DOI: 10.11992/tis.201906039 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20190722.1416.004.html 基于渗流模型的影响力最大化算法 花勇，陈伯伦，朱国畅，袁燕，金鹰 （淮阴工学院 计算机与软件工程学院，江苏 淮安 223003） 摘 要：多数社交网络影响力最大化算法的研究只关注于所选种子节点集合的影响力是否最优，忽略网络自身 传播影响力的固有能力。本文对网络进行渗流模拟，计算渗流后网络的主连通分量随着传播概率改变的趋势， 并且求得主连通分量大小增加开始变快的相变点，从而计算网络自身传播影响力的固有能力。通过相变值与 种子节点集合大小的换算，求得当前网络最佳的种子节点集合大小。将种子节点集合大小限制在最佳大小范 围内即可获得最佳的影响力。在 kareteclub、football、highschool 和 socdolphins 社交网络数据集上进行实验，验 证了该方法的有效性。 关键词：社交网络；影响力最大化；种子节点集合；渗流；传播概率；主连通分量；相变点；相变值 中图分类号：TP301.6 文献标志码：A 文章编号：1673−4785(2019)06−1262−09 中文引用格式：花勇, 陈伯伦, 朱国畅, 等. 基于渗流模型的影响力最大化算法 [J]. 智能系统学报, 2019, 14(6): 1262–1270. 英文引用格式：HUA Yong, CHEN Bolun, ZHU Guochang, et al. An influence maximization algorithm based on percolation model[J]. CAAI transactions on intelligent systems, 2019, 14(6): 1262–1270. An influence maximization algorithm based on percolation model HUA Yong，CHEN Bolun，ZHU Guochang，YUAN Yan，JIN Yin (School of Computer and Software Engineering, Huaiyin Institute of Technology, Huaian 223003, China) Abstract: Most of the influence maximization algorithms in social networks only focus on whether the influence of the seed node set selected is the optimal, and ignore the inherent ability of social network’s propagating influence. Using percolation simulation, we calculate the change trend of the giant component of the network generation after percolation with propagation probability, and derive the starting point at which the size of the giant component increases fastest, that is, the phase point. The phase value shows the inherent ability of the network propagating influence. The optimal seed set size of the network can be calculated through conversion of the phase value and the size of the seed set. We can obtain the optimal influence by limiting the size of the seed set to the optimal size. We performed experiments on karate club, football, high school, and soc-dolphins, verifying the effectiveness of the algorithm. Keywords: social network; influence maximization; seed set; percolation; propagation probability; giant component; phase point; phase value 随着社交网络中信息量的快速增长，信息传 播速度的不断加快，其信息传播构建了一种分布 式传播机制[1] 以及节点的合作机制[2] ，即信息在 用户之间的扩散会受到用户影响力的影响[3]。因 此，开展影响力分析研究显得十分重要。影响力 最大化问题是影响力分析的重要课题之一。2015 年，Morone 和 Makse 在 Nature 上对社交网络中影 响力最大化问题进行了深入探讨[4]。影响力最大 化问题解决的是如何衡量网络中节点重要性的问 题，其经典应用之一是病毒营销[5-8] ，也就是通过 口口相传效应进行产品的销售[9-10]。 影响力最大化问题最早由 Kempe 等 [11] 率先 提出。Kempe 等使用独立级联模型与线性阈值模 型对社交网络中影响力的传播进行建模，并且证 收稿日期：2019−06−21. 网络出版日期：2019−07−23. 基金项目：国家自然科学基金项目 (61602202)；江苏省自然科 学基金项目 (BK20160428). 通信作者：陈伯伦. E-mail：chenbolun1986@163.com. 第 14 卷第 6 期 智 能 系 统 学 报 Vol.14 No.6 2019 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2019
第6期 花勇，等：基于渗流模型的影响力最大化算法 ·1263· 明在社交网络中寻找具有最佳影响力的种子节点 能力的角度出发研究影响力最大化问题，从而得 集合是NP-Hard问题。而且他们提出使用简单的 出网络所适合的种子节点集合的大小。本文提出 贪婪算法寻找具有最佳影响力的种子节点集合， 种子节点集合大小并不是越大越好，而是每个网 获得了(1-l/e)的近似保证。影响力最大化问题中 络都存在一个种子节点个数的上限，一旦超过这 的关键问题是如何衡量节点传播影响力的能力， 个上限，随着种子节点个数大小的增加，种子节 也就是节点所具有的影响力。在最初的影响力最 点集合的影响力是趋于饱和的。为研究网络传播 大化问题研究中，一些基于网络拓扑结构的中心 影响力的固有能力，本文使用渗流42的思想，即 性方法被提出，例如度中心性和点介数中心性。 对网络进行渗流模拟，得出网络由大量零散的团 在随后的影响力最大化问题研究中，多数算法使 块趋向于形成一个主团块的相变值，从而得出网 用次模性质2，即通过大量迭代来计算边际收 络所适合的种子节点集合的大小，即提出一种基 益，从而近似求得问题的最优解，但是存在算法 于渗流模型的影响力最大化种子节点集合大小选 时间复杂度较高的问题。Chen等uo提出了度折 取算法来获得最优的种子节点集合大小，并对算 损启发式算法，即优先选择度大的节点作为种子 法结果进行了分析。 节点，一旦某节点被选取为种子节点，那么其邻 居节点被选为种子节点的概率将大大降低。 1问题描述 Lee等切利用多数节点平均只能影响到2阶邻居 1.1影响力最大化问题 节点的现象，提出了2-hop贪婪算法，即利用节点 本文主要研究无向网络传播影响力的能力， 在2阶邻居范围内的影响力更新节点的边际收 定义无向网络G=(V,E),其中V为无向网络G中 益。Chen等提出MA(maximum influence arbor- 的节点集合，E为无向网络G中边的集合。定义 escence)最大影响力树算法，利用MA(maximum =I为网络G的节点个数，m=E为网络G边的个 influence in-arborescence)影响力最大入树和MI- 数。影响力最大化问题就是在网络G中寻找大 OA(maximum out-arborescence)影响力最大出树构 小为k的种子节点集合，使得这个种子节点在 建节点的影响力传播路径，通过节点的影响力最 网络G中传播的影响力是最大的，我们定义种子 大化路径计算得分并选取种子节点，相较于原始 节点集合为S。在影响力最大化问题中，我们面 的贪婪算法取得了较低的时间复杂度，但因为 临着两个尤为重要的问题，即影响力是如何定义 MIA需要对每个节点建立树，所以空间复杂度相 的，以及影响力在网络中是如何传播的。独立级 较于其他算法较高。JUNK等I提出IRIE(influ-- 联模型(independent cascade model)是经典的模拟 ence ranking influence estimation)算法，即算法整体 影响力传播的模型，在之前多数影响力最大化问 被分为两部分，影响力排名使用一种算法，影响 题的研究中，研究人员都使用独立级联模型作为 力模拟再使用一种算法。在最近影响力最大化问 影响力传播模型。而节点或者节点集合的影响 题的研究中，许多优秀的算法被提出，其中Kt 力，我们使用影响力函数进行求解。 sak等)提出最具影响力的节点往往不是具有较 1.2独立级联模型 大连接的节点，而是处于网络核心位置的节点， 独立级联模型22是经典的用于模拟影响力 通过k-shell分解2o分析网络中节点核数与节点 传播的算法，模型描述如下：在网络G中，节点集 影响力的关系，为影响力最大化问题提供了新的 合V中的节点v存在两种状态，即一种是激活状 解决思路。Gao等2根据节点的影响力与其局部 态另一种是未激活状态。假设1时刻，节点v已 结构的关系，提出了一种局部结构中心性的方 经处于激活状态，那么节点ⅴ会尝试以概率p去 法，利用节点以及其邻居的拓扑结构和中心性来 激活其邻居节点u,如果激活成功，那么节点“会 衡量节点的影响力，此算法在评估节点影响力方 从+1时刻开始，一直处于激活状态。如果激活 面更加准确。王等提出的多种群随机差分粒 失败，那么从什1时刻开始，节点再也不能被节 子群优化算法和刘等2)提出的改进萤火虫算法 点ⅴ尝试激活。我们定义影响力传播模型的初始 也可很好的应用到影响力最大化问题当中。 时刻为=0时刻，定义集合A。中的节点处于激活 在上述的影响力最大化算法中，研究人员只 状态，那么集合A,为1时刻被激活的节点集合。 关注所选种子节点影响力是否最佳，旨在研究更 如果存在某一时刻c+1,集合A1为空集，那么独 加优秀的算法近似求得影响力最优的种子节点集 立级联模型终止运行。当独立级联模型终止时， 合，而忽略了种子节点集合的大小和网络固有的 我们可以获得在此过程中激活的节点集合A= 传播影响力能力的关系。本文从网络传播影响力 {Ao,A1,A2,…,Ac}g
明在社交网络中寻找具有最佳影响力的种子节点 集合是 NP-Hard 问题。而且他们提出使用简单的 贪婪算法寻找具有最佳影响力的种子节点集合， 获得了 (1-1/e) 的近似保证。影响力最大化问题中 的关键问题是如何衡量节点传播影响力的能力， 也就是节点所具有的影响力。在最初的影响力最 大化问题研究中，一些基于网络拓扑结构的中心 性方法被提出，例如度中心性和点介数中心性。 在随后的影响力最大化问题研究中，多数算法使 用次模性质[12-15] ，即通过大量迭代来计算边际收 益，从而近似求得问题的最优解，但是存在算法 时间复杂度较高的问题。Chen 等 [16] 提出了度折 损启发式算法，即优先选择度大的节点作为种子 节点，一旦某节点被选取为种子节点，那么其邻 居节点被选为种子节点的概率将大大降低。 Lee 等 [17] 利用多数节点平均只能影响到 2 阶邻居 节点的现象，提出了 2-hop 贪婪算法，即利用节点 在 2 阶邻居范围内的影响力更新节点的边际收 益。Chen 等 [16] 提出 MIA(maximum influence arborescence) 最大影响力树算法，利用 MIIA(maximum influence in-arborescence) 影响力最大入树和 MIOA(maximum out-arborescence) 影响力最大出树构 建节点的影响力传播路径，通过节点的影响力最 大化路径计算得分并选取种子节点，相较于原始 的贪婪算法取得了较低的时间复杂度，但因为 MIA 需要对每个节点建立树，所以空间复杂度相 较于其他算法较高。JUNK 等 [18] 提出 IRIE(influence ranking influence estimation) 算法，即算法整体 被分为两部分，影响力排名使用一种算法，影响 力模拟再使用一种算法。在最近影响力最大化问 题的研究中，许多优秀的算法被提出，其中 Kitsak 等 [19] 提出最具影响力的节点往往不是具有较 大连接的节点，而是处于网络核心位置的节点， 通过 k-shell 分解[20] 分析网络中节点核数与节点 影响力的关系，为影响力最大化问题提供了新的 解决思路。Gao 等 [21] 根据节点的影响力与其局部 结构的关系，提出了一种局部结构中心性的方 法，利用节点以及其邻居的拓扑结构和中心性来 衡量节点的影响力，此算法在评估节点影响力方 面更加准确。王等[22] 提出的多种群随机差分粒 子群优化算法和刘等[23] 提出的改进萤火虫算法 也可很好的应用到影响力最大化问题当中。 在上述的影响力最大化算法中，研究人员只 关注所选种子节点影响力是否最佳，旨在研究更 加优秀的算法近似求得影响力最优的种子节点集 合，而忽略了种子节点集合的大小和网络固有的 传播影响力能力的关系。本文从网络传播影响力 能力的角度出发研究影响力最大化问题，从而得 出网络所适合的种子节点集合的大小。本文提出 种子节点集合大小并不是越大越好，而是每个网 络都存在一个种子节点个数的上限，一旦超过这 个上限，随着种子节点个数大小的增加，种子节 点集合的影响力是趋于饱和的。为研究网络传播 影响力的固有能力，本文使用渗流[24-26] 的思想，即 对网络进行渗流模拟，得出网络由大量零散的团 块趋向于形成一个主团块的相变值，从而得出网 络所适合的种子节点集合的大小，即提出一种基 于渗流模型的影响力最大化种子节点集合大小选 取算法来获得最优的种子节点集合大小，并对算 法结果进行了分析。 1 问题描述 1.1 影响力最大化问题 本文主要研究无向网络传播影响力的能力， 定义无向网络 G=(V,E)，其中 V 为无向网络 G 中 的节点集合，E 为无向网络 G 中边的集合。定义 n=|V|为网络 G 的节点个数，m=|E|为网络 G 边的个 数。影响力最大化问题就是在网络 G 中寻找大 小为 k 的种子节点集合，使得这 k 个种子节点在 网络 G 中传播的影响力是最大的，我们定义种子 节点集合为 S。在影响力最大化问题中，我们面 临着两个尤为重要的问题，即影响力是如何定义 的，以及影响力在网络中是如何传播的。独立级 联模型 (independent cascade model) 是经典的模拟 影响力传播的模型，在之前多数影响力最大化问 题的研究中，研究人员都使用独立级联模型作为 影响力传播模型。而节点或者节点集合的影响 力，我们使用影响力函数进行求解。 1.2 独立级联模型 Atotal = {A0,A1,A2,··· ,Ac} 独立级联模型[27-28] 是经典的用于模拟影响力 传播的算法，模型描述如下：在网络 G 中，节点集 合 V 中的节点 v 存在两种状态，即一种是激活状 态另一种是未激活状态。假设 t 时刻，节点 v 已 经处于激活状态，那么节点 v 会尝试以概率 p 去 激活其邻居节点 u，如果激活成功，那么节点 u 会 从 t+1 时刻开始，一直处于激活状态。如果激活 失败，那么从 t+1 时刻开始，节点 u 再也不能被节 点 v 尝试激活。我们定义影响力传播模型的初始 时刻为 t=0 时刻，定义集合 A0 中的节点处于激活 状态，那么集合 At 为 t 时刻被激活的节点集合。 如果存在某一时刻 c+1，集合 Ac+1 为空集，那么独 立级联模型终止运行。当独立级联模型终止时， 我们可以获得在此过程中激活的节点集合 。 第 6 期 花勇，等：基于渗流模型的影响力最大化算法 ·1263·
·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，如果 prp，那么此边处于非占有状态，也 就是此边从网络中删除。通过改变统一的传播概 率值 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 卷
第6期 花勇，等：基于渗流模型的影响力最大化算法 ·1265· 5)函数avg(x)用于计算矩阵每列的平均值， 中节点的总数，边数为网络中边的总数，最大度 所以此步骤是对传播概率p下R个num(GP)求 数为网络中边数的最大值，平均度为度的平均 平均值，并且存入到C中，也就是说，每个传播概 值。同配系数是描述大度节点之间相连接的能 率P,我们都会对G'进行R次渗流模拟，从而产 力，其值越靠近1说明其同配性越好；聚类系数是 生R个num(GP),最后将其求平均，即得到每个 描述节点之间连接成团的能力，其值越大说明网 传播概率p所对应GP的平均大小； 络中的节点更有可能产生连接：网络密度描述了 6)采用多项式拟合的方法对pa和C进行拟 网络实际存在边数与网络可容纳边数的比值，也 合。多项式拟合是使用多项展开式去近似数据点 就是节点之间相互连边的密集程度，其值越大说 的函数关系，并使用最小二乘法来得到多项展开 明网络越密集。 式的系数，最终求得数据点函数关系的方法。多 表1数据集属性 项式拟合公式为 Table 1 The attributes of datasets F(x)=ao+ax+ax2+...+ax (1) 最大平均同配聚类网络 数据集 节点数边数 式中：a到a为使用最小二乘法求取的系数；I为 度数度数系数系数密度 多项式的阶数。本文式(I)中的x为Pt中的元 KarateClub 34 78 17 4.59-0.480.570.14 素，C中的元素为F(x)的函数值，通过多项式拟合 Football 115 613 1210.660.160.40 0.09 函数求得F(x)的系数，从而求得P和C的拟合 HighSchool 134 406 176.060.290.540.05 函数Fx: SocDolphins 62 159125.13-0.040.260.08 7)求函数Fx)的导函数dF(x: 8)相变值p。在pm的左邻域中，其中dF(pm)的 在现有影响力最大化问题的研究中，大多数 值为函数dF(x)的最大值，dF(P)的值为靠近 研究人员主要关注如何在网络中选取具有最佳影 dFPm)最近的最小值，相变值P,为函数Fx)变化 响力的种子节点集合，也就是通过研究创造出更 速率开始加快的起点位置； 先进的影响力最大化算法来近似选取种子节点集 9)求取最优种子集合大小。 合，并不关注种子节点集合大小的问题，即网络 传播影响力的固有能力的问题。本文主要研究网 ●●●● 络传播影响力的能力，提出网络传播影响力的能 ● 力是有限的，也就是在网络中选择种子节点的时 (a)2维晶格网络(b)p=0.1 (c)p=0.4 (d)p=0.6 候并不是越多越好，每个网络存在一个最优的种 图1渗流实验例图 子集合大小，一旦种子集合大小超过了最优值， Fig.1 The example of percolation experiment 其多出的种子节点所带来的影响力几乎不能起到 3实验结果及分析 积极的作用，反而会增加实验的成本。因为本文 主要研究种子节点集合的大小，所以需要获得种 本文提出的一种基于渗流模型的影响力最大 子节点的算法作为载体来求得种子节点，本文使 化种子节点集合大小选取算法在4个公共数据集 用4种经典的算法来选取种子节点，4种算法分 上进行实验，数据集分别为KarateClub29、Foot 别为：贪婪算法、度中心性、点介数中心性和基于 ball、HighSchool和SocDolphins!。因本文主 k核过滤核覆盖算法。使用上述方法分别选出 要研究无向网络，所以必要时对数据集进行了无 4个数据集具有最佳影响力的10种子节点，并对 向化处理。KarateClub数据集是1970年美国大学 生空手道俱乐部34名成员之间朋友关系的社交 其影响力做出分析。 网络。Football是2000年美式足球秋季常规赛大 3.1渗流实验 学之间的比赛网络。HighSchool是2013年12月 我们提出网络传播影响力的固有能力与相变 法国马赛高中学生友谊联系的社交网络。Soc 值P.有关，所以在网络G上进行渗流实验。通过 Dophins是宽吻海豚之间的社交网络。其中数据 改变传播概率P,对网络G进行多次渗流实验，建 集KarateClub、HighSchool和SocDophins中的边 立传播概率p与渗流后网络GP的最大连通子图 表示成员之间拥有相对频繁的联系，Football数据 GP平均大小s的函数关系。在具体实验中，设定 集中的边表示球队之间会有比赛安排。不同数据 传播概率p为0.001~1的数，且为0.001的倍数， 集的拓扑属性如表1中所示，其中节点数为网络 也就是说传播概率p有1000种情况。然后根据
5) 函数 avg(x) 用于计算矩阵每列的平均值， 所以此步骤是对传播概率 p 下 R 个 num(GP') 求 平均值，并且存入到 C'中，也就是说，每个传播概 率 p，我们都会对 G'进行 R 次渗流模拟，从而产 生 R 个 num(GP')，最后将其求平均，即得到每个 传播概率 p 所对应 GP'的平均大小； 6) 采用多项式拟合的方法对 plist 和 C'进行拟 合。多项式拟合是使用多项展开式去近似数据点 的函数关系，并使用最小二乘法来得到多项展开 式的系数，最终求得数据点函数关系的方法。多 项式拟合公式为 F(x) = a0 +a1 x+a2 x 2 +···+alx l (1) 式中：a0 到 al 为使用最小二乘法求取的系数；l 为 多项式的阶数。本文式 (1) 中的 x 为 plist 中的元 素，C'中的元素为 F(x) 的函数值，通过多项式拟合 函数求得 F(x) 的系数，从而求得 plist 和 C'的拟合 函数 F(x)； 7) 求函数 F(x) 的导函数 dF(x)； 8) 相变值 pc 在 pm 的左邻域中，其中 dF(pm) 的 值为函数 dF(x) 的最大值， dF(pc ) 的值为靠近 dF(pm) 最近的最小值，相变值 pc 为函数 F(x) 变化 速率开始加快的起点位置； 9) 求取最优种子集合大小。 (a) 2维晶格网络 (b) p=0.1 (c) p=0.4 (d) p=0.6 图 1 渗流实验例图 Fig. 1 The example of percolation experiment 3 实验结果及分析 本文提出的一种基于渗流模型的影响力最大 化种子节点集合大小选取算法在 4 个公共数据集 上进行实验，数据集分别为 KarateClub[29] 、Football[30] 、HighSchool[31] 和 SocDolphins[32]。因本文主 要研究无向网络，所以必要时对数据集进行了无 向化处理。KarateClub 数据集是 1970 年美国大学 生空手道俱乐部 34 名成员之间朋友关系的社交 网络。Football 是 2000 年美式足球秋季常规赛大 学之间的比赛网络。HighSchool 是 2013 年 12 月 法国马赛高中学生友谊联系的社交网络。SocDophins 是宽吻海豚之间的社交网络。其中数据 集 KarateClub、HighSchool 和 SocDophins 中的边 表示成员之间拥有相对频繁的联系，Football 数据 集中的边表示球队之间会有比赛安排。不同数据 集的拓扑属性如表 1 中所示，其中节点数为网络 中节点的总数，边数为网络中边的总数，最大度 数为网络中边数的最大值，平均度为度的平均 值。同配系数是描述大度节点之间相连接的能 力，其值越靠近 1 说明其同配性越好；聚类系数是 描述节点之间连接成团的能力，其值越大说明网 络中的节点更有可能产生连接；网络密度描述了 网络实际存在边数与网络可容纳边数的比值，也 就是节点之间相互连边的密集程度，其值越大说 明网络越密集。 表 1 数据集属性 Table 1 The attributes of datasets 数据集 节点数 边数 最大 度数 平均 度数 同配 系数 聚类 系数 网络 密度 KarateClub 34 78 17 4.59 −0.48 0.57 0.14 Football 115 613 12 10.66 0.16 0.40 0.09 HighSchool 134 406 17 6.06 0.29 0.54 0.05 SocDolphins 62 159 12 5.13 −0.04 0.26 0.08 在现有影响力最大化问题的研究中，大多数 研究人员主要关注如何在网络中选取具有最佳影 响力的种子节点集合，也就是通过研究创造出更 先进的影响力最大化算法来近似选取种子节点集 合，并不关注种子节点集合大小的问题，即网络 传播影响力的固有能力的问题。本文主要研究网 络传播影响力的能力，提出网络传播影响力的能 力是有限的，也就是在网络中选择种子节点的时 候并不是越多越好，每个网络存在一个最优的种 子集合大小，一旦种子集合大小超过了最优值， 其多出的种子节点所带来的影响力几乎不能起到 积极的作用，反而会增加实验的成本。因为本文 主要研究种子节点集合的大小，所以需要获得种 子节点的算法作为载体来求得种子节点，本文使 用 4 种经典的算法来选取种子节点，4 种算法分 别为：贪婪算法、度中心性、点介数中心性和基于 k 核过滤核覆盖算法。使用上述方法分别选出 4 个数据集具有最佳影响力的 10 种子节点，并对 其影响力做出分析。 3.1 渗流实验 我们提出网络传播影响力的固有能力与相变 值 pc 有关，所以在网络 G 上进行渗流实验。通过 改变传播概率 p，对网络 G 进行多次渗流实验，建 立传播概率 p 与渗流后网络 GP 的最大连通子图 GP'平均大小 s 的函数关系。在具体实验中，设定 传播概率 p 为 0.001~1 的数，且为 0.001 的倍数， 也就是说传播概率 p 有 1 000种情况。然后根据 第 6 期 花勇，等：基于渗流模型的影响力最大化算法 ·1265·
·1266· 智能系统学报 第14卷 不同的传播概率p对网络进行渗流实验，并且每 R次渗流模拟后所得的最大连通子图大小均值。 个传播概率p进行R次独立的渗流实验，因为渗 图2中蓝色部分是由1000个点构成的散点图，每 流实验具有随机性，本文中通过设置较高的R值 个点对应了一个传播概率p以及一个最大连通子 来获取足够的实验结果，本文设置R=1000。渗流 图大小均值s。图中红色曲线是对p和s进行拟 实验后，计算得到渗流后网络GP的最大连通子 合得到的拟合函数F(x)的曲线。由图2发现随 图GP的平均大小s,通过多项式拟合的方法对 着p值的增大，曲线逐渐平缓，在p值较小的时 p和s进行拟合，形成p和s的拟合函数F(x)。渗 候，s的增长速率较大。即p值较小时，GP由零 流模拟实验具体结果如图2所示。在图2中， 散的小团块组成，当p值越来越大时，G趋向由 p表示网络的传播概率，s表示每个传播概率p下 主团块组成。 0 150 0 100 20 50 10 0 0.2 0.40.60.81.0 0 0.20.40.60.81.0 (a)KarateClub (b)Football 150 80 100 40 20 0 0.20.40.60.8 1.0 0 0.2 0.40.60.81.0 P (c)Highschool (d)Socdolphins 图2渗流实验 Fig.2 The percolation experiment 3.2相变值 由主团块组成，GP逐渐呈现出以最大连通子图为 为了计算网络G的相变值p,需要计算函数 主的图结构。本文提出相变值P。反应了网络 F(x)的变化速率。在图3中，p为传播概率，r为 G传播影响力的固有能力，也就是相变值反应网 函数F(x)的变化速率，即函数dF(x)的值。我们 络G中边被激活的能力，即在影响力传播模型 可以得到函数dF(x)的最大值dF(Pm),点Pm为 下，被激活边占总边数的比例。因此可以得到网 图3中绿色的点，也就是函数Fx)变化最快的时 络G最优的种子节点集合的大小k'。 候。所有找的相变点Pe,在pm的左邻域中，也就 因此可以计算出4个数据集的相变值与最优 是图3中红色的点，其中dF(P)为距离dF(pm)最 的种子节点集合的大小，其中KarateClub、Foot- 近的最小值，也就是函数dF(x)变化增长到最快 ball、HighSchool和SocDolphins的相变值分别为 时的起点位置。当网络的传播概率p小于相变 0.034、0.059、0.022和0.029。KarateClub、Foot- 值P。时，变化速率r还处于较低水平，GP由零散 ball、HighSchool和SocDolphins的最优的种子节 的小团块组成，当传播概率p大于P时，GP趋向 点集合的大小分别为2、7、3和2。 80 1000 500 .40 0.2 -500 0.4 0.6 0.8 1.0 0.2 0.4 0.6 0.8 1.0 (a)KarateClub (b)Football
不同的传播概率 p 对网络进行渗流实验，并且每 个传播概率 p 进行 R 次独立的渗流实验，因为渗 流实验具有随机性，本文中通过设置较高的 R 值 来获取足够的实验结果，本文设置 R=1 000。渗流 实验后，计算得到渗流后网络 GP 的最大连通子 图 GP'的平均大小 s，通过多项式拟合的方法对 p 和 s 进行拟合，形成 p 和 s 的拟合函数 F(x)。渗 流模拟实验具体结果如图 2 所示。在图 2 中 ， p 表示网络的传播概率，s 表示每个传播概率 p 下 R 次渗流模拟后所得的最大连通子图大小均值。 图 2 中蓝色部分是由 1 000 个点构成的散点图，每 个点对应了一个传播概率 p 以及一个最大连通子 图大小均值 s。图中红色曲线是对 p 和 s 进行拟 合得到的拟合函数 F(x) 的曲线。由图 2 发现随 着 p 值的增大，曲线逐渐平缓，在 p 值较小的时 候，s 的增长速率较大。即 p 值较小时，GP 由零 散的小团块组成，当 p 值越来越大时，GP 趋向由 主团块组成。 0 10 20 30 40 0.2 0.4 p s (a) KarateClub 0.6 0.8 1.0 50 100 150 s (c) Highschool 0 0.2 0.4 p 0.6 0.8 1.0 20 40 60 80 s (d) Socdolphins 0 0.2 0.4 p 0.6 0.8 1.0 50 100 150 s (b) Football 0 0.2 0.4 p 0.6 0.8 1.0 图 2 渗流实验 Fig. 2 The percolation experiment 3.2 相变值 为了计算网络 G 的相变值 pc，需要计算函数 F(x) 的变化速率。在图 3 中，p 为传播概率，r 为 函数 F(x) 的变化速率，即函数 dF(x) 的值。我们 可以得到函数 dF(x) 的最大值 dF(pm)，点 pm 为 图 3 中绿色的点，也就是函数 F(x) 变化最快的时 候。所有找的相变点 pc，在 pm 的左邻域中，也就 是图 3 中红色的点，其中 dF(pc ) 为距离 dF(pm) 最 近的最小值，也就是函数 dF(x) 变化增长到最快 时的起点位置。当网络的传播概率 p 小于相变 值 pc 时，变化速率 r 还处于较低水平，GP 由零散 的小团块组成，当传播概率 p 大于 pc 时，GP 趋向 由主团块组成，GP 逐渐呈现出以最大连通子图为 主的图结构。本文提出相变值 pc 反应了网络 G 传播影响力的固有能力，也就是相变值反应网 络 G 中边被激活的能力，即在影响力传播模型 下，被激活边占总边数的比例。因此可以得到网 络 G 最优的种子节点集合的大小 k'。 因此可以计算出 4 个数据集的相变值与最优 的种子节点集合的大小，其中 KarateClub、Football、HighSchool 和 SocDolphins 的相变值分别为 0.034、0.059、0.022 和 0.029。KarateClub、Football、HighSchool 和 SocDolphins 的最优的种子节 点集合的大小分别为 2、7、3 和 2。 (a) KarateClub r 0 20 40 60 80 0.2 0.4 p 0.6 0.8 1.0 (b) Football r 0 −500 0 500 1 000 0.2 0.4 p 0.6 0.8 1.0 ·1266· 智 能 系 统 学 报 第 14 卷
第6期 花勇，等：基于渗流模型的影响力最大化算法 ·1267 600 200 400 150 200 100 0 2000 0.2 0.40.6 0.81.0 0.2 0.40.6 0.81.0 D (c)Highschool (d)Socdolphins 图3拟合函数变化速率 Fig.3 7 The changing rate of fitting function 3.3影响力模拟 进行影响力模拟。4个数据集种子节点集合影响 本文使用4种影响力最大化算法来选取种子 力实验结果如图4所示。在图4中，k为种子节点 节点集合，4种算法分别是：简单贪婪算法山、度 个数，I(k)为种子节点集合的影响力。图4(a)为 中心性、点介数中心性B)以及基于k核过滤核覆 KarateClub数据集种子节点集合影响力的实验结 盖算法。其中，简单贪婪算法通过迭代的方式 果，在图中我们可以发现4种算法选出的种子节 逐节点计算I(SU{w),并在每轮迭代中将使函数 点集合在大小为3时，影响力大小几乎趋于平衡， 说明当前数据集适合3个以下种子节点作为种子 值最大的节点加入到种子节点集合S中，直到 节点集合。图4(b)为Football数据集种子节点集 选满k个种子节点，迭代结束。度中心性和点介 合影响力的实验结果，4种算法的影响力呈逐渐 数中心性则选择度最大的k个节点作为种子节 上升趋势，并且在种子节点个数为6时，增长趋势 点。基于k核过滤核覆盖算法则是通过预先计算 逐渐变缓。图4(c)为HighSchool数据集种子节点 出最优的核数kp,通过k核分解出最小核数为 集合影响力的实验结果，4种算法的影响力呈逐 k的子图，在子图中选择核数最大的节点作为种 渐上升趋势，图像在种子节点个数k分别为6时 子节点。 上升趋势逐渐放缓。图4(d)为SocDolphins数据 在影响力模拟实验中，我们使用独立级联模 集种子节点集合影响力的实验结果，4种算法的 型作为影响力模拟算法以及使用I(x)计算影响 影响力波动较大，总体呈上升趋势，但我们可以 力，并且使用上述4种算法选取影响力最大的 观察到当=5开始，影响力已经开始小于种子节 10个种子节点，分别对1~10大小种子节点集合 点的个数。 口简单贪婪算法 口简单贪婪算法 ▣度中心性 15r☐度中心性 ☐点介数中心性 □点介数中心性 6 ☐基于核过滤核覆盖算法 ☐基于k核过滤核覆盖算法 0 6 10 (a)KarateClub (b)Football ☐简单贪婪算法 ☐简单贪婪算法 12 ▣度中心性 ☐度中心性 10 点介数中心性 口点介数中心性 ☐基于k核过滤核覆盖算法 ☐基于k核过滤核覆盖算法 6 4 10 (c)HighSchool (d)SocDolphins 图4影响力模拟 Fig.4 The influence simulation
3.3 影响力模拟 I(S ∪ {v}) 本文使用 4 种影响力最大化算法来选取种子 节点集合，4 种算法分别是：简单贪婪算法[11] 、度 中心性、点介数中心性[33] 以及基于 k 核过滤核覆 盖算法[34]。其中，简单贪婪算法通过迭代的方式 逐节点计算 ，并在每轮迭代中将使函数 值最大的节点 v 加入到种子节点集合 S 中，直到 选满 k 个种子节点，迭代结束。度中心性和点介 数中心性则选择度最大的 k 个节点作为种子节 点。基于 k 核过滤核覆盖算法则是通过预先计算 出最优的核数 kopt，通过 k 核分解出最小核数为 kopt 的子图，在子图中选择核数最大的节点作为种 子节点。 在影响力模拟实验中，我们使用独立级联模 型作为影响力模拟算法以及使用 I(x) 计算影响 力，并且使用上述 4 种算法选取影响力最大的 10 个种子节点，分别对 1~10 大小种子节点集合 进行影响力模拟。4 个数据集种子节点集合影响 力实验结果如图 4 所示。在图 4 中，k 为种子节点 个数，I(k) 为种子节点集合的影响力。图 4(a) 为 KarateClub 数据集种子节点集合影响力的实验结 果，在图中我们可以发现 4 种算法选出的种子节 点集合在大小为 3 时，影响力大小几乎趋于平衡， 说明当前数据集适合 3 个以下种子节点作为种子 节点集合。图 4(b) 为 Football 数据集种子节点集 合影响力的实验结果，4 种算法的影响力呈逐渐 上升趋势，并且在种子节点个数为 6 时，增长趋势 逐渐变缓。图 4(c) 为 HighSchool数据集种子节点 集合影响力的实验结果，4 种算法的影响力呈逐 渐上升趋势，图像在种子节点个数 k 分别为 6 时 上升趋势逐渐放缓。图 4(d) 为 SocDolphins 数据 集种子节点集合影响力的实验结果，4 种算法的 影响力波动较大，总体呈上升趋势，但我们可以 观察到当 k=5 开始，影响力已经开始小于种子节 点的个数。 (a) KarateClub 0 2 4 k 简单贪婪算法 度中心性 点介数中心性 基于k核过滤核覆盖算法 6 8 10 I(k) 2 4 6 8 (d) SocDolphins 0 2 4 k 简单贪婪算法 度中心性 点介数中心性 基于k核过滤核覆盖算法 6 8 10 I(k) 2 4 6 8 (b) Football 0 2 4 k 简单贪婪算法 度中心性 点介数中心性 基于k核过滤核覆盖算法 6 8 10 I(k) 5 10 15 (c) HighSchool 0 2 4 k 简单贪婪算法 度中心性 点介数中心性 基于k核过滤核覆盖算法 6 8 10 I(k) 4 2 10 8 6 12 图 4 影响力模拟 Fig. 4 The influence simulation (c) Highschool r 0 −200 0 200 400 600 0.2 0.4 p 0.6 0.8 1.0 (d) Socdolphins r 0 50 100 150 200 0.2 0.4 p 0.6 0.8 1.0 图 3 拟合函数变化速率 Fig. 3 The changing rate of fitting function 第 6 期 花勇，等：基于渗流模型的影响力最大化算法 ·1267·
·1268· 智能系统学报 第14卷 3.4平均影响力分析 中可以发现，当=1时单个种子节点的平均影响 在图5中，k为种子节点个数，纵坐标为当前 力是最高的，1个种子节点平均影响力为2个节 种子节点集合单个节点的平均影响力。从图5(a) 点左右，当心3时，我们发现种子节点的平均影响 中可以发现，当=2时单个种子节点的平均影响 力已经不足1.5个，所以我们认为HighSchool数 力是最高的，1个种子节点平均影响力1.5个节点 据集适合选取3个种子节点作为种子节点集合比 左右。当心4时，单个种子节点的影响力不足于 较合适。从图5()中可以发现，1个种子节点平 1个节点。所以KarateClub数据集适合选择2个 均影响力最高为1个节点左右。点介数算法选取 种子节点作为种子节点集合较合适。从图5(b)中 的种子节点在k心1时就出现了平均影响力的下 可以发现，当k为1~3时，种子节点的平均影响力 降，贪婪算法和度中心性算法选出的种子节点的 最大，1个种子节点平均影响2个节点，当 影响力分别在k为4和3时出现下降，因此Soc k>6时，发现种子节点的平均影响力已经不足 Dolphins数据集适合选择2个种子节点作为种子 1.5个，所以我们认为Football数据集适合选取 节点集合比较合适。 7个种子节点作为种子节点集合比较合适。从图5c) 2.0 ☐简单贪婪算法 ☐简单贪婪算法 ☐度中心性 ☐度中心性 5 一点介数中心性 口点介数中心性 ]基于核过滤核覆盖算法 ☐基于k核过滤核覆盖算法 6 8 10 6 10 (a)KarateClub (b)Football 2.5 口简单贪婪算法 2.0 ☐简单贪婪算法 ☐度中心性 2.0 口点介数中心性 度中心性 1.5 ☐点介数中心性 5 ☐基于k核过滤核覆盖算法 m ☐基于k核过滤核覆盖算法 0.5 4 6 0 4 k (c)HighSchool (d)SocDolphins 图5平均影响力 Fig.5 The average influence 通过实验可以看出，一个网络的种子节点集 能力，并提出一种基于渗流模型的影响力最大化 合大小并不是越大越好，而是存在一个上限，当 算法来选取网络所适合的种子节点集合的大小。 种子节点集合的大小超出了这个上限，多出的种 在算法中，我们建立传播概率与渗流模拟后网络 子节点并不能带来很好的边际收益。根据我们所 最大连通子图大小的关系，得到网络相变值P。 提出的算法计算出的最优种子节点集合大小k', 当传播概率p大于p时，渗流后网络倾向于由一 基本反映了一个网络传播影响力能力的上限，因 个主团块组成，当传播概率p等于p。时，网络由 此为种子节点个数的选取提供了很好的参考，并 多个大型团块组成。算法通过相变值与种子节点 且可以用于一些选取最优种子节点集合算法中， 集合大小的换算，得到当前网络最优的种子节点 减少额外的时间开支。 集合大小。实验结果表明该临界点对影响力最大 4结束语 化种子节点集合的大小选取起着重要的指导性 作用。 本文主要对无向网络传播影响力的固有能力 参考文献： 进行研究，通过对网络进行渗流模拟得到网络的 相变值，发现相变值可以反应网络传播影响力的 [1]BOND R M,FARISS C J,JONES JJ,et al.A 61-million-
3.4 平均影响力分析 在图 5 中，k 为种子节点个数，纵坐标为当前 种子节点集合单个节点的平均影响力。从图 5(a) 中可以发现，当 k=2 时单个种子节点的平均影响 力是最高的，1 个种子节点平均影响力 1.5 个节点 左右。当 k>4 时，单个种子节点的影响力不足于 1 个节点。所以 KarateClub 数据集适合选择 2 个 种子节点作为种子节点集合较合适。从图 5(b) 中 可以发现，当 k 为 1~3 时，种子节点的平均影响力 最大， 1 个种子节点平均影 响 2 个节点， 当 k>6 时，发现种子节点的平均影响力已经不足 1.5 个，所以我们认为 Football 数据集适合选取 7 个种子节点作为种子节点集合比较合适。从图 5(c) 中可以发现，当 k=1 时单个种子节点的平均影响 力是最高的，1 个种子节点平均影响力为 2 个节 点左右，当 k>3 时，我们发现种子节点的平均影响 力已经不足 1.5 个，所以我们认为 HighSchool 数 据集适合选取 3 个种子节点作为种子节点集合比 较合适。从图 5(d) 中可以发现，1 个种子节点平 均影响力最高为 1 个节点左右。点介数算法选取 的种子节点在 k>1 时就出现了平均影响力的下 降，贪婪算法和度中心性算法选出的种子节点的 影响力分别在 k 为 4 和 3 时出现下降，因此 SocDolphins 数据集适合选择 2 个种子节点作为种子 节点集合比较合适。 简单贪婪算法 度中心性 点介数中心性 基于k核过滤核覆盖算法 (a) KarateClub 0 2 4 k 6 8 10 平均影响力 0.5 1.0 1.5 2.0 简单贪婪算法 度中心性 点介数中心性 基于k核过滤核覆盖算法 (d) SocDolphins 0 2 4 k 6 8 10 平均影响力 0.5 1.0 1.5 简单贪婪算法 2.0 度中心性 点介数中心性 基于k核过滤核覆盖算法 (c) HighSchool 0 2 4 k 6 8 10 平均影响力 0.5 1.0 1.5 2.5 2.0 简单贪婪算法 度中心性 点介数中心性 基于k核过滤核覆盖算法 (b) Football 0 2 4 k 6 8 10 平均影响力 1 2 3 图 5 平均影响力 Fig. 5 The average influence 通过实验可以看出，一个网络的种子节点集 合大小并不是越大越好，而是存在一个上限，当 种子节点集合的大小超出了这个上限，多出的种 子节点并不能带来很好的边际收益。根据我们所 提出的算法计算出的最优种子节点集合大小 k'， 基本反映了一个网络传播影响力能力的上限，因 此为种子节点个数的选取提供了很好的参考，并 且可以用于一些选取最优种子节点集合算法中， 减少额外的时间开支。 4 结束语 本文主要对无向网络传播影响力的固有能力 进行研究，通过对网络进行渗流模拟得到网络的 相变值，发现相变值可以反应网络传播影响力的 能力，并提出一种基于渗流模型的影响力最大化 算法来选取网络所适合的种子节点集合的大小。 在算法中，我们建立传播概率与渗流模拟后网络 最大连通子图大小的关系，得到网络相变值 pc。 当传播概率 p 大于 pc 时，渗流后网络倾向于由一 个主团块组成，当传播概率 p 等于 pc 时，网络由 多个大型团块组成。算法通过相变值与种子节点 集合大小的换算，得到当前网络最优的种子节点 集合大小。实验结果表明该临界点对影响力最大 化种子节点集合的大小选取起着重要的指导性 作用。 参考文献： [1] BOND R M, FARISS C J, JONES J J, et al. A 61-million- ·1268· 智 能 系 统 学 报 第 14 卷
第6期 花勇，等：基于渗流模型的影响力最大化算法 ·1269· person experiment in social influence and political mobiliz- Polyhedral Combinatorics:Dedicated to the Memory of ation[J.Nature,2012,489(7415):295-298. D.R.Fulkerson.Berlin,Heidelberg:Springer,1978: [2]蒋庆丰，门朝光，田泽宇，等.社会感知的延迟容忍网络 73-87. 节点合作机制[.哈尔滨工程大学学报，2017,38(6)： [14]CORNUEJOLS G,FISHER ML,NEMHAUSER G L. 921-930 Location of bank accounts to optimize float:an analytic JIANG Qingfeng,MEN Chaoguang,TIAN Zeyu,et al.A study of exact and approximate algorithms[J].Manage- social-aware node cooperation mechanism for DTN[J]. ment science,.1977,23(8):789-810. Journal of Harbin Engineering University,2017,38(6): [15]WILLIAMS H P.Integer and combinatorial 921-930 optimization[J].Journal of the operational research soci- [3]LU Zaixin,FAN Lidan,WU Weili,et al.Efficient influ- ety,1990,41(2):177-178. ence spread estimation for influence maximization under [16]CHEN Wei,WANG Chi,WANG Yajun.Scalable influ- the linear threshold model[J].Computational social net- ence maximization for prevalent viral marketing in large- works,2014,1:2 scale social networks[Cl//Proceedings of the 16th ACM [4]MORONE F,MAKSE H A.Corrigendum:influence max- SIGKDD International Conference on Knowledge Dis- imization in complex networks through optimal percola- covery and Data Mining.Washington,USA,2010:1029- tion[J.Nature,2015,527(7579:544. 1038. [5]ZHU Zhiguo.Discovering the influential users oriented to [17]LEE J R,CHUNG C W.A fast approximation for influ- viral marketing based on online social networks[J].Phys- ence maximization in large social networks[Cl//Proceed- ica A:statistical mechanics and its applications,2013, ings of the 23rd International Conference on World Wide 392(16):3459-3469 Web.Seoul,Korea,2014:1157-1162. [6]SADOVYKH V,SUNDARAM D,PIRAMUTHU S.Do [18]JUNG K,HEO W.CHEN Wei.IRIE:scalable and robust online social networks support decision-making?[J].De- influence maximization in social networks[C]//Proceed- cision support systems,2015,70:15-30. ings of IEEE 12th International Conference on Data Min- [7]SCHMITT P,SKIERA B,VAN DEN BULTE C.Referral ing.Brussels,Belgium,2012:918-923. programs and customer value[J].Journal of marketing, [19]KITSAK M.GALLOS L K.HAVLIN S.et al.Identifica- 2011,75(1):46-59 tion of influential spreaders in complex networks[J] [8]VERBRAKEN T,GOETHALS F,VERBEKE W,et al. Nature physics,2010,6(11):888-893. Predicting online channel acceptance with social network [20]CARMI S,HAVLIN S,KIRKPATRICK S,et al.A mod- data[J].Decision support systems,2014,63:104-114. el of Internet topology using k-shell decomposition[J]. [9]GUILLE A.HACID H,FAVRE C,et al.Information dif- Proceedings of the national academy of sciences of the fusion in online social networks:a survey[J].ACM SIG- United States of America,2007,104(27):11150-11154. MOD record,2013,42(1)上17-28. [21]GAO Shuai,MA Jun,CHEN Zhumin,et al.Ranking the [10]GOLDENBERG J,LIBAI B,MULLER E.Talk of the spreading ability of nodes in complex networks based on network:a complex systems look at the underlying pro- local structure[J].Physica A:statistical mechanics and its cess of word-of-mouth[J].Marketing letters,2001,12(3): applications,.2014,403:130-147. 211-223 [22]王皓，高立群，欧阳海滨.多种群随机差分粒子群优化 [11]KEMPE D.KLEINBERG J,TARDOS E.Maximizing the 算法及其应用.哈尔滨工程大学学报，2017,38(4)： spread of influence through a social network[Cl//Proceed- 652-660. ings of the 9th ACM SIGKDD International Conference WANG Hao,GAO Liqun,OUYANG Haibin.Multi-pop- on Knowledge Discovery and Data Mining.Washington, ulation random differential particle swarm optimization USA,2003:137-146. and its application[J].Journal of Harbin Engineering Uni- [12]NEMHAUSER G L,WOLSEY L A,FISHER M L.An versity.,2017.38(4:652-660 analysis of approximations for maximizing submodular [23]刘畅，刘利强，张丽娜，等.改进萤火虫算法及其在全局 set functions-I[J].Mathematical programming,1978, 优化问题中的应用】.哈尔滨工程大学学报，2017， 14(1:265-294 38(4):569-577. [13]FISHER ML.NEMHAUSER G L.WOLSEY L A.An LIU CHANG,LIU Liqiang,ZHANG Lina,et al.An im- analysis of approximations for maximizing submodular proved firefly algorithm and its application in global op- set functions-II[M]//BALINSKI M L,HOFFMAN A J. timization[J].Journal of Harbin Engineering University
person experiment in social influence and political mobilization[J]. Nature, 2012, 489(7415): 295–298. 蒋庆丰, 门朝光, 田泽宇, 等. 社会感知的延迟容忍网络 节点合作机制 [J]. 哈尔滨工程大学学报, 2017, 38(6): 921–930. JIANG Qingfeng, MEN Chaoguang,TIAN Zeyu,et al. A social-aware node cooperation mechanism for DTN[J]. Journal of Harbin Engineering University, 2017, 38(6): 921–930. [2] LU Zaixin, FAN Lidan, WU Weili, et al. Efficient influence spread estimation for influence maximization under the linear threshold model[J]. Computational social networks, 2014, 1: 2. [3] MORONE F, MAKSE H A. Corrigendum: influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 527(7579): 544. [4] ZHU Zhiguo. Discovering the influential users oriented to viral marketing based on online social networks[J]. Physica A: statistical mechanics and its applications, 2013, 392(16): 3459–3469. [5] SADOVYKH V, SUNDARAM D, PIRAMUTHU S. Do online social networks support decision-making?[J]. Decision support systems, 2015, 70: 15–30. [6] SCHMITT P, SKIERA B, VAN DEN BULTE C. Referral programs and customer value[J]. Journal of marketing, 2011, 75(1): 46–59. [7] VERBRAKEN T, GOETHALS F, VERBEKE W, et al. Predicting online channel acceptance with social network data[J]. Decision support systems, 2014, 63: 104–114. [8] GUILLE A, HACID H, FAVRE C, et al. Information diffusion in online social networks: a survey[J]. ACM SIGMOD record, 2013, 42(1): 17–28. [9] GOLDENBERG J, LIBAI B, MULLER E. Talk of the network: a complex systems look at the underlying process of word-of-mouth[J]. Marketing letters, 2001, 12(3): 211–223. [10] KEMPE D, KLEINBERG J, TARDOS É. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, USA, 2003: 137–146. [11] NEMHAUSER G L, WOLSEY L A, FISHER M L. An analysis of approximations for maximizing submodular set functions-I[J]. Mathematical programming, 1978, 14(1): 265–294. [12] FISHER M L, NEMHAUSER G L, WOLSEY L A. An analysis of approximations for maximizing submodular set functions-II[M]//BALINSKI M L, HOFFMAN A J. [13] Polyhedral Combinatorics: Dedicated to the Memory of D. R. Fulkerson. Berlin, Heidelberg: Springer, 1978: 73–87. CORNUEJOLS G, FISHER M L, NEMHAUSER G L. Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms[J]. Management science, 1977, 23(8): 789–810. [14] WILLIAMS H P. Integer and combinatorial optimization[J]. Journal of the operational research society, 1990, 41(2): 177–178. [15] CHEN Wei, WANG Chi, WANG Yajun. Scalable influence maximization for prevalent viral marketing in largescale social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, USA, 2010: 1029- 1038. [16] LEE J R, CHUNG C W. A fast approximation for influence maximization in large social networks[C]//Proceedings of the 23rd International Conference on World Wide Web. Seoul, Korea, 2014: 1157–1162. [17] JUNG K, HEO W, CHEN Wei. IRIE: scalable and robust influence maximization in social networks[C]//Proceedings of IEEE 12th International Conference on Data Mining. Brussels, Belgium, 2012: 918–923. [18] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nature physics, 2010, 6(11): 888–893. [19] CARMI S, HAVLIN S, KIRKPATRICK S, et al. A model of Internet topology using k-shell decomposition[J]. Proceedings of the national academy of sciences of the United States of America, 2007, 104(27): 11150–11154. [20] GAO Shuai, MA Jun, CHEN Zhumin, et al. Ranking the spreading ability of nodes in complex networks based on local structure[J]. Physica A: statistical mechanics and its applications, 2014, 403: 130–147. [21] 王皓, 高立群, 欧阳海滨. 多种群随机差分粒子群优化 算法及其应用 [J]. 哈尔滨工程大学学报, 2017, 38(4): 652–660. WANG Hao, GAO Liqun, OUYANG Haibin. Multi-population random differential particle swarm optimization and its application[J]. Journal of Harbin Engineering University, 2017, 38(4): 652–660. [22] 刘畅, 刘利强, 张丽娜, 等. 改进萤火虫算法及其在全局 优化问题中的应用 [J]. 哈尔滨工程大学学报, 2017, 38(4): 569–577. LIU CHANG, LIU Liqiang, ZHANG Lina, et al. An improved firefly algorithm and its application in global optimization[J]. Journal of Harbin Engineering University, [23] 第 6 期 花勇，等：基于渗流模型的影响力最大化算法 ·1269·
·1270· 智能系统学报 第14卷 2017,38(4)569-577 can geographic isolation explain this unique trait?[].Be- [24]JI Shenggong,LU Linyuan,YEUNG C H,et al.Effective havioral ecology and sociobiology,2003,54(4):396-405. spreading from multiple leaders identified by percolation [33]FREEMAN L C.A set of measures of centrality based on in the susceptible-infected-recovered (SIR)model[J]. betweenness[J].Sociometry,1977,40(1):35-41. New journal of physics,2017,19(7):073020. [34]李阅志，祝园园，钟鸣.基于k核过滤的社交网络影响 [25]NEWMAN M E J.Spread of epidemic disease on net- 最大化算法J.计算机应用，2018.38(2少：464-470. works[J].Physical review E,2002,66(1):016128. LI Yuezhi,ZHU Yuanyuan,ZHONG Ming.k-core [26]MORONE F.MAKSE HA.Influence maximization in filtered influence maximization algorithms in social net- complex networks through optimal percolation[J].Nature, works[J].Journal of computer applications,2018,38(2): 2015,524(7563):65-68 464-470. [27]CHEN Shuo,FAN Ju,LI Guoliang,et al.Online topic- 作者简介： aware influence maximization[J].Proceedings of the 花勇，男，1994年生，硕士研究 VLDB endowment,2015,8(6):666-677. 生，主要研究方向为影响力最大化与 [28]LIU Bo,CONG Gao,XU Dong,et al.Time constrained 复杂网络。 influence maximization in social networks[C]//Proceed- ings of IEEE 12th International Conference on Data Min- ing.Brussels,Belgium,2012:439-448. [29]ZACHARY WW.An information flow model for con- flict and fission in small groups[J].Journal of anthropolo- 陈伯伦，男，1986年生，讲师，博 gical research,1977,33(4):452-473. 士，主要研究方向为链接预测、推荐系 [30]GIRVAN M,NEWMAN M E J.Community structure in 统和数据挖掘。主持国家自然科学基 金青年基金、江苏省自然科学基金青年 social and biological networks[J].Proceedings of the na- tional academy of sciences of the United States of Amer- 基金多项。发表学术论文30余篇。 ica2001,9912):7821-7826. [31]ROSSANA M,JULIE F,ALAIN B,et al.Contact pat- terns in a high school:a comparison between data collec- 朱国畅，男，1996年生，硕士研究 ted using wearable sensors,contact diaries and friendship 生，主要研究方向为人工智能、数据挖 掘与机器学习。 surveys[J].PLoS one,2015,10(9):e0136497. [32]LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations:
2017, 38(4): 569–577. JI Shenggong, LÜ Linyuan, YEUNG C H, et al. Effective spreading from multiple leaders identified by percolation in the susceptible-infected-recovered (SIR) model[J]. New journal of physics, 2017, 19(7): 073020. [24] NEWMAN M E J. Spread of epidemic disease on networks[J]. Physical review E, 2002, 66(1): 016128. [25] MORONE F, MAKSE H A. Influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 524(7563): 65–68. [26] CHEN Shuo, FAN Ju, LI Guoliang, et al. Online topicaware influence maximization[J]. Proceedings of the VLDB endowment, 2015, 8(6): 666–677. [27] LIU Bo, CONG Gao, XU Dong, et al. Time constrained influence maximization in social networks[C]//Proceedings of IEEE 12th International Conference on Data Mining. Brussels, Belgium, 2012: 439–448. [28] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research, 1977, 33(4): 452–473. [29] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the national academy of sciences of the United States of America, 2001, 99(12): 7821–7826. [30] ROSSANA M, JULIE F, ALAIN B, et al. Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys[J]. PLoS one, 2015, 10(9): e0136497. [31] LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations: [32] can geographic isolation explain this unique trait?[J]. Behavioral ecology and sociobiology, 2003, 54(4): 396–405. FREEMAN L C. A set of measures of centrality based on betweenness[J]. Sociometry, 1977, 40(1): 35–41. [33] 李阅志, 祝园园, 钟鸣. 基于 k-核过滤的社交网络影响 最大化算法 [J]. 计算机应用, 2018, 38(2): 464–470. LI Yuezhi, ZHU Yuanyuan, ZHONG Ming. k-core filtered influence maximization algorithms in social networks[J]. Journal of computer applications, 2018, 38(2): 464–470. [34] 作者简介： 花勇，男，1994 年生，硕士研究 生，主要研究方向为影响力最大化与 复杂网络。 陈伯伦，男，1986 年生，讲师，博 士，主要研究方向为链接预测、推荐系 统和数据挖掘。主持国家自然科学基 金青年基金、江苏省自然科学基金青年 基金多项。发表学术论文 30 余篇。 朱国畅，男，1996 年生，硕士研究 生，主要研究方向为人工智能、数据挖 掘与机器学习。 ·1270· 智 能 系 统 学 报 第 14 卷