·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 时出现下降，因此 Soc￾Dolphins 数据集适合选择 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 卷