第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] 、Foot￾ball[30] 、HighSchool[31] 和 SocDolphins[32]。因本文主 要研究无向网络，所以必要时对数据集进行了无 向化处理。KarateClub 数据集是 1970 年美国大学 生空手道俱乐部 34 名成员之间朋友关系的社交 网络。Football 是 2000 年美式足球秋季常规赛大 学之间的比赛网络。HighSchool 是 2013 年 12 月 法国马赛高中学生友谊联系的社交网络。Soc￾Dophins 是宽吻海豚之间的社交网络。其中数据 集 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·