第2期 张学龙，等：链路预测下能源供应链网络合作演化机制研究 .225, restart,RWR)。RWR指标假设随机游走粒子在每 AUC值波动幅度最小，提高了实验的准确性和可靠 走一步的时候都以一定概率返回初始位置。设粒子 性；利用路径相似指标的LP指标预测效果好于 返回概率为p,P为网络概率返回矩阵，其元素 Katz指标，也就是在该能源供应链网络中考虑局部 P=a,k表示节点U处的粒子下一步到节点心， 路径的效果明显好于考虑全部路径，其中LP指标 的概率，如果两者相连ay=1,否则a,=0。某粒子 预测效果也是5组指标中精确度第2的指标：基于 初始时刻在节点v,处，那么t+1时刻该粒子到达网 局部信息相似指标的PA指标预测的精确度大于 络每个节点概率向量为 CN指标的精确度，但是PA指标的实验数据方差较 π(t+1)=(1-p)Pπ(t)+pex (6) 大，也就是再次进行实验时可能导致PA指标平均 式中：e,表示一个一维列向量且仅有第x个元素为 精确度值变化较大：CN指标预在能源供应链中预 1,其他元素都为0。不难得到式(6)的稳定解为 测合作的效果最差，和其他4个指标相比，精确度之 T.=p(E-(1-p)P)-1e (7) 差相差甚大。在此特别说明的是，表2中精确度的 式中：π为节点)出发的粒子最终有多少概率走 平均值并不是绝对的，也就是说，假如再一次进行 到节点)，，由此定义RWR相似性为 200组独立实验时，计算的结果可能会发生改变，但 SR= (8) 是通过各自方差可知变化浮动不会太大。 2.3相似性算法精确度分析 表25种相似性算法预测精确度和方差 表1中所示该能源供应链共66条连边，不存在 Table 2 The prediction accuracy and variance of five kinds of similarity algorithms 自环（没有单独的点），而20个节点的网络在理论 上的链接边数为20×[(20-1)/2]=190条，当前已 算法名称 精确度 方差 知链接数为66，未知链接数为190-66=124。假设 共同邻居(CN) 0.7374 0.0093 测试集比例为10%，训练集则为90%，对测试集和 偏好连接(PA) 0.7593 0.0104 训练集进行一次性划分，在划分的同时需要保证训 局部路径(LP) 0.7603 0.0090 练集的连通性。测试集中的测试边的数目为66× 全部路径(Katz) 0.7465 0.0095 10%≈7，最精确的方法是将所有的测试边和不存在 重启的随机游走(RWVR) 0.7952 0.0071 的边都进行比较，共有比较次数为7×124=868次， 为了丰富算法的选择，将5种指标算法进行相 因为计算机程序代码设计的是随机抽样，为了使得 互结合，以便观察两种指标耦合后预测效果好还是 AUC尽可能接近真实值，本文采取抽样次数为 单独利用相似性指标效果好。本文设计的是：经过 200000次，并进行200次独立实验，计算出的AUC 计算后的精确度最高的RWR指标与其他4种指标 值等于200000次抽样200次独立实验的平均数。 分别耦合从而进行链路预测，也就是将基于随机游 计算AUC值的过程类似于伯努利实验， 走的指标与路径相似性指标、局部信息相似性指标 200000次随机抽样的结果不相互影响，忽略比较得 进行耦合。采用的是最简单的线性方式，即 分相等的情况下，计算AUC值时得分为1的概率为 s=x×sRwB+(1-x)s0T (9) p,则得分为0的概率为1-p。如此地进行n次抽 式中：swR是基于RWR指标，sQT是基于其他4种 样得到的AUC值为M/n,抽样次数越多AUC值越 结构性指标，参数x∈[0,1]，当x=1时，算法回归 接近p。那么，最佳的抽样次数是能够接受的概率 到swWR,当x=0时，算法回归到sr。 无限接近于p的最小n值。设LP指标和Katz指标 式(9)中实际上是对计算机程序中指标算法的 中可调参数a=0.O01,RWR指标中的粒子返回概率 得分进行重新计算，为了统一标准，将每种相似性指 p=0.95,5种相似性算法在能源供应链中预测的 标得分值作归一化处理，即每组数据都除以组别数 AUC值平均值和方差如表2所示。 据中的最大值。值得注意的是，所有算法最后的链 由表2看出，当单独以5种指标作为相似性算 接边的得分都是在训练集的基础上计算出来的，也 法时，RWR指标的精确度AUC为0.7952是最高 就是在训练集和测试集划分后，原网络的链接情况 的，说明通过RWR指标进行能源供应链节点企业 就是去掉测试集中的边剩下训练集的边，测试集中 合作预测更符合网络特征，对于合作演化的机制具 边和不存在链接一样不存在了，预测的时候只可以 有较高的精确性，而且平均方差σ=0.0071，在5种 应用训练集中的信息。 指标中也是最小的，意味着200组独立实验计算的 参数x的区间为[0.1,0.95]，步长为0.05，分ｒｅｓｔａｒｔ，ＲＷＲ）。 ＲＷＲ 指标假设随机游走粒子在每 走一步的时候都以一定概率返回初始位置。 设粒子 返回概率为 ρ ， Ｐ 为网络概率返回矩阵， 其元素 Ｐｉｘｙ ＝ａｘｙ ／ ｋｘ 表示节点 ｖｘ 处的粒子下一步到节点 ｖｙ 的概率，如果两者相连 ａｘｙ ＝ １，否则 ａｘｙ ＝ ０。 某粒子 初始时刻在节点 ｖｘ 处，那么 ｔ ＋ １ 时刻该粒子到达网 络每个节点概率向量为 πｘ（ｔ ＋ １） ＝ （１ － ρ）Ｐ Ｔπｘ（ｔ） ＋ ρｅｘ （６） 式中： ｅｘ 表示一个一维列向量且仅有第 ｘ 个元素为 １，其他元素都为 ０。 不难得到式（６）的稳定解为 πｘ ＝ ρ （Ｅ － （１ － ρ）Ｐ Ｔ ） － １ｅｘ （７） 式中： πｘｙ 为节点 ｖｘ 出发的粒子最终有多少概率走 到节点 ｖｙ ，由此定义 ＲＷＲ 相似性为 ｓ ＲＷＲ ｘｙ ＝ πｘｙ ＋ πｙｘ （８） ２．３ 相似性算法精确度分析 表 １ 中所示该能源供应链共 ６６ 条连边，不存在 自环（没有单独的点），而 ２０ 个节点的网络在理论 上的链接边数为 ２０×［（２０－１） ／ ２］ ＝ １９０ 条，当前已 知链接数为 ６６，未知链接数为 １９０－６６ ＝ １２４。 假设 测试集比例为 １０％，训练集则为 ９０％，对测试集和 训练集进行一次性划分，在划分的同时需要保证训 练集的连通性。 测试集中的测试边的数目为 ６６ × １０％≈７，最精确的方法是将所有的测试边和不存在 的边都进行比较，共有比较次数为 ７×１２４ ＝ ８６８ 次， 因为计算机程序代码设计的是随机抽样，为了使得 ＡＵＣ 尽可能接近 真 实 值， 本 文 采 取 抽 样 次 数 为 ２００ ０００次，并进行 ２００ 次独立实验，计算出的 ＡＵＣ 值等于 ２００ ０００ 次抽样 ２００ 次独立实验的平均数。 计算 ＡＵＣ 值 的 过 程 类 似 于 伯 努 利 实 验， ２００ ０００次随机抽样的结果不相互影响，忽略比较得 分相等的情况下，计算 ＡＵＣ 值时得分为 １ 的概率为 ｐ ，则得分为 ０ 的概率为 １ － ｐ 。 如此地进行 ｎ 次抽 样得到的 ＡＵＣ 值为 Ｍ／ ｎ，抽样次数越多 ＡＵＣ 值越 接近 ｐ 。 那么，最佳的抽样次数是能够接受的概率 无限接近于 ｐ 的最小 ｎ 值。 设 ＬＰ 指标和 Ｋａｔｚ 指标 中可调参数 α ＝ ０．００１，ＲＷＲ 指标中的粒子返回概率 ρ ＝ ０．９５，５ 种相似性算法在能源供应链中预测的 ＡＵＣ 值平均值和方差如表 ２ 所示。 由表 ２ 看出，当单独以 ５ 种指标作为相似性算 法时，ＲＷＲ 指标的精确度 ＡＵＣ 为 ０． ７９５ ２ 是最高 的，说明通过 ＲＷＲ 指标进行能源供应链节点企业 合作预测更符合网络特征，对于合作演化的机制具 有较高的精确性，而且平均方差 σ ＝ ０．００７ １，在 ５ 种 指标中也是最小的，意味着 ２００ 组独立实验计算的 ＡＵＣ 值波动幅度最小，提高了实验的准确性和可靠 性；利用路径相似指标的 ＬＰ 指标预测效果好于 Ｋａｔｚ 指标，也就是在该能源供应链网络中考虑局部 路径的效果明显好于考虑全部路径，其中 ＬＰ 指标 预测效果也是 ５ 组指标中精确度第 ２ 的指标；基于 局部信息相似指标的 ＰＡ 指标预测的精确度大于 ＣＮ 指标的精确度，但是 ＰＡ 指标的实验数据方差较 大，也就是再次进行实验时可能导致 ＰＡ 指标平均 精确度值变化较大；ＣＮ 指标预在能源供应链中预 测合作的效果最差，和其他 ４ 个指标相比，精确度之 差相差甚大。 在此特别说明的是，表 ２ 中精确度的 平均值并不是绝对的，也就是说，假如再一次进行 ２００ 组独立实验时，计算的结果可能会发生改变，但 是通过各自方差可知变化浮动不会太大。 表 ２ ５ 种相似性算法预测精确度和方差 Ｔａｂｌｅ ２ Ｔｈｅ ｐｒｅｄｉｃｔｉｏｎ ａｃｃｕｒａｃｙ ａｎｄ ｖａｒｉａｎｃｅ ｏｆ ｆｉｖｅ ｋｉｎｄｓ ｏｆ ｓｉｍｉｌａｒｉｔｙ ａｌｇｏｒｉｔｈｍｓ 算法名称 精确度 方差 共同邻居（ＣＮ） ０．７３７ ４ ０．００９ ３ 偏好连接（ＰＡ） ０．７５９ ３ ０．０１０ ４ 局部路径（ＬＰ） ０．７６０ ３ ０．００９ ０ 全部路径（Ｋａｔｚ） ０．７４６ ５ ０．００９ ５ 重启的随机游走（ＲＷＲ） ０．７９５ ２ ０．００７ １ 为了丰富算法的选择，将 ５ 种指标算法进行相 互结合，以便观察两种指标耦合后预测效果好还是 单独利用相似性指标效果好。 本文设计的是：经过 计算后的精确度最高的 ＲＷＲ 指标与其他 ４ 种指标 分别耦合从而进行链路预测，也就是将基于随机游 走的指标与路径相似性指标、局部信息相似性指标 进行耦合。 采用的是最简单的线性方式，即 ｓ ＝ ｘ × ｓ ＲＷＲ ＋ （１ － ｘ）ｓ ＱＴ （９） 式中： ｓ ＲＷＲ 是基于 ＲＷＲ 指标， ｓ ＱＴ 是基于其他 ４ 种 结构性指标，参数 ｘ ∈ ［０，１］ ，当 ｘ ＝ １ 时，算法回归 到 ｓ ＲＷＲ ，当 ｘ ＝ ０ 时，算法回归到 ｓ ＱＴ 。 式（９）中实际上是对计算机程序中指标算法的 得分进行重新计算，为了统一标准，将每种相似性指 标得分值作归一化处理，即每组数据都除以组别数 据中的最大值。 值得注意的是，所有算法最后的链 接边的得分都是在训练集的基础上计算出来的，也 就是在训练集和测试集划分后，原网络的链接情况 就是去掉测试集中的边剩下训练集的边，测试集中 边和不存在链接一样不存在了，预测的时候只可以 应用训练集中的信息。 参数 ｘ 的区间为 ［０．１，０．９５］ ，步长为 ０．０５，分 第 ２ 期 张学龙，等：链路预测下能源供应链网络合作演化机制研究 ·２２５·