·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、Foot￾ball、HighSchool 和 SocDolphins 的相变值分别为 0.034、0.059、0.022 和 0.029。KarateClub、Foot￾ball、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 卷