第2期 张学龙，等：链路预测下能源供应链网络合作演化机制研究 .223. 不是每个节点之间都存在链接关系。根据已知网络 点，该网络在理论上存在的连边数是5×(5-1)/2= 属性，对于给定一种链路预测的算法，为每对没有连 10,其中7条是已知的，剩下3条为不存在的边。为 边的节点x、y赋予一个分数值，该分数值表示一种 了验证链路预测算法的精确性，需要在7条已知边 节点连边关系的相似性，它与节点间链接概率正相 中选择部分构成E,假如选择边{2,4}和{2,5} 关，分数值越大，两点链接的可能性就越大。将所有 作为测试边，如图1(b)所示，则剩下的5条已知边 未链接的节点对按照该分数值从大到小进行排序， 则构成E。在链路预测方法中，只应用E中边的 排序越靠前的节点相互链接的概率越大。 信息，上述中的E中的边仅是随机从已知边中选取 为了测试相似性指标预测的准确性，一般将已 的，若再进行下一次验证精确性选择，则测试边不一 知的连边E分为两个部分：训练集E和测试集E。 定是{2,4}和{2,5}，而是E中的任何边都可能 显然，E=EUE,E∩E=⑦。在此，将属于U 被选出作为测试边，E中的边只是暂时被“待定”。 但不属于E的边称为不存在的边，称为J,属于U但 根据链路预测算法得到剩下5条未知边的得分值分 不属于E的边为未知边，称为H。 别为s5=4,524=4.5,514=3.8,54=4.6,s5=4,那 衡量链路预测算法精确度的指标主要有AU、 么在计算AUC时需将未知边按照其得分排序： Precision和RankingScore。这3个指标对预测精确 54<s25=535<s24<s4,再根据上述AUC计算公 度衡量的侧重点不同，其中AUC是最常见的一种衡 式，得AUC=(1+0.5+1+1)/(2×3)=0.583。 量指标，它从整体上衡量算法的精确度[2o]:Precision 由此可以说明，当选择E中的边个数发生变化 只考虑排在前L位的边是否预测准确[2]：而Rank- 时，AUC值会相应地变化，即使E完全相同时， ingScore则更多考虑了所预测边的排序[2a)。文中选 AUC值也会不同。因为AUC计算公式中的n是抽 择的衡量算法精确度的指标为AUC,AUC是在E 样次数，抽样方式有多种类型，如随机抽样、逐项遍 中随机选择一条边的分数值比随机选择的一条不存 历、滚雪球抽样等，由5个节点构成的能源供应链中 在的边的分数值高的概率)。每次随机从E中选 n=6,其含义是测试边和不存在的边比较了6次。 一条边，再从J中随机选择一条边，若E中选择边 而在文中利用计算机程序计算AUC值时，比较的边 的分数值大于J中选择边的分数，那么就加1分：若 (预测边和不存在边的比较)是随机抽取的，因此即 两个分数值相等就加0.5分：若小于就不加分。这 便E中信息完全一样，抽样次数和抽样比较对象不 样独立比较n次，如果有M次E中的边分数值大于 同导致AUC值变化，为了使得到的AUC越接近真 J分数值，有Z次两分数值相等，AUC的计算式如式 实值，抽样次数n越大越好。 (1)所示。 AUC =(M+0.5Z)/n (1) 2能源供应链网络合作演化分析 假设所有分数都是随机产生的，因此AUC≈ 本文运用链路预测对能源供应链合作演化进行 0.5,当AUC≥0.5时，大于的程度衡量了算法在多 研究，将能源供应链网络中节点内外部信息量化，对 大程度上比随机选择的方法要精确。为了进一步说 量化后的数据进行划分，再利用相似性指标对预测 明AUC指标的含义，假设由5个节点构成的能源供 进行得分，最后使用AUC评价指标对预测的精确性 应链网络，其结构图如图1所示。 进行对比分析。 2.1能源供应链网络结构 一个简单无向无权网络，由点和边构成，需要满 足以下4个条件： 1)节点自身不可以与自身连接： 2)节点间最多只有一条连线，不可出现多条连边； 3)连边不具有方向性： a完整网络结构 b)测试网络结构 4)连边只代表节点间关系，代表的是合作的关 图15个节点能源供应链网络结构 系，没有对应的权重。 Fig.1 Network structure of five node energy supply chains 本文分析的能源供应链由20个节点企业构成， 图1表示一个完整的供应链网络结构，实线表 将其分别编号为1,2，…，20，其节点链接表示其长 示训练集，虚线表示测试集。该网络中包含5个节 期合作情况，如表1所示。不是每个节点之间都存在链接关系。 根据已知网络 属性，对于给定一种链路预测的算法，为每对没有连 边的节点 ｘ 、 ｙ 赋予一个分数值，该分数值表示一种 节点连边关系的相似性，它与节点间链接概率正相 关，分数值越大，两点链接的可能性就越大。 将所有 未链接的节点对按照该分数值从大到小进行排序， 排序越靠前的节点相互链接的概率越大。 为了测试相似性指标预测的准确性，一般将已 知的连边 Ｅ 分为两个部分：训练集 Ｅ Ｔ 和测试集 Ｅ Ｐ 。 显然， Ｅ ＝ Ｅ Ｔ ∪ Ｅ Ｐ ， Ｅ Ｔ ∩ Ｅ Ｐ ＝ ⌀ 。 在此，将属于 Ｕ 但不属于 Ｅ 的边称为不存在的边，称为 Ｊ ，属于 Ｕ 但 不属于 Ｅ Ｔ 的边为未知边，称为 Ｈ 。 衡量链路预测算法精确度的指标主要有 ＡＵ、 Ｐｒｅｃｉｓｉｏｎ 和 ＲａｎｋｉｎｇＳｃｏｒｅ。 这 ３ 个指标对预测精确 度衡量的侧重点不同，其中 ＡＵＣ 是最常见的一种衡 量指标，它从整体上衡量算法的精确度［２０］ ；Ｐｒｅｃｉｓｉｏｎ 只考虑排在前 Ｌ 位的边是否预测准确［２１］ ；而 Ｒａｎｋ⁃ ｉｎｇＳｃｏｒｅ 则更多考虑了所预测边的排序［２２］ 。 文中选 择的衡量算法精确度的指标为 ＡＵＣ，ＡＵＣ 是在 Ｅ Ｐ 中随机选择一条边的分数值比随机选择的一条不存 在的边的分数值高的概率［２３］ 。 每次随机从 Ｅ Ｐ 中选 一条边，再从 Ｊ 中随机选择一条边，若 Ｅ Ｐ 中选择边 的分数值大于 Ｊ 中选择边的分数，那么就加 １ 分；若 两个分数值相等就加 ０．５ 分；若小于就不加分。 这 样独立比较 ｎ 次，如果有 Ｍ 次 Ｅ Ｐ 中的边分数值大于 Ｊ 分数值，有 Ｚ 次两分数值相等，ＡＵＣ 的计算式如式 （１）所示。 ＡＵＣ ＝ （Ｍ ＋ ０．５Ｚ） ／ ｎ （１） 假设所有分数都是随机产生的，因此 ＡＵＣ ≈ ０．５ ，当 ＡＵＣ ≥ ０．５ 时，大于的程度衡量了算法在多 大程度上比随机选择的方法要精确。 为了进一步说 明 ＡＵＣ 指标的含义，假设由 ５ 个节点构成的能源供 应链网络，其结构图如图 １ 所示。 图 １ ５ 个节点能源供应链网络结构 Ｆｉｇ．１ Ｎｅｔｗｏｒｋ ｓｔｒｕｃｔｕｒｅ ｏｆ ｆｉｖｅ ｎｏｄｅ ｅｎｅｒｇｙ ｓｕｐｐｌｙ ｃｈａｉｎｓ 图 １ 表示一个完整的供应链网络结构，实线表 示训练集，虚线表示测试集。 该网络中包含 ５ 个节 点，该网络在理论上存在的连边数是５×（５－１） ／ ２ ＝ １０，其中 ７ 条是已知的，剩下 ３ 条为不存在的边。 为 了验证链路预测算法的精确性，需要在 ７ 条已知边 中选择部分构成 Ｅ Ｐ ，假如选择边 ｛２，４｝ 和 ｛２，５｝ 作为测试边，如图 １（ ｂ）所示，则剩下的 ５ 条已知边 则构成 Ｅ Ｔ 。 在链路预测方法中，只应用 Ｅ Ｔ 中边的 信息，上述中的 Ｅ Ｐ 中的边仅是随机从已知边中选取 的，若再进行下一次验证精确性选择，则测试边不一 定是 ｛２，４｝ 和 ｛２，５｝ ，而是 Ｅ Ｔ 中的任何边都可能 被选出作为测试边， Ｅ Ｔ 中的边只是暂时被“待定”。 根据链路预测算法得到剩下 ５ 条未知边的得分值分 别为 ｓ２５ ＝ ４， ｓ２４ ＝ ４．５， ｓ１４ ＝ ３．８， ｓ３４ ＝ ４．６， ｓ３５ ＝ ４，那 么在计算 ＡＵＣ 时需将未知边按照其得分排序： ｓ１４ ＜ ｓ２５ ＝ ｓ３５ ＜ ｓ２４ ＜ ｓ３４ ，再根据上述 ＡＵＣ 计算公 式，得 ＡＵＣ ＝ （１＋０．５＋１＋１） ／ （２×３）＝ ０．５８３。 由此可以说明，当选择 Ｅ Ｐ 中的边个数发生变化 时，ＡＵＣ 值会相应地变化，即使 Ｅ Ｐ 完全相同时， ＡＵＣ 值也会不同。 因为 ＡＵＣ 计算公式中的 ｎ 是抽 样次数，抽样方式有多种类型，如随机抽样、逐项遍 历、滚雪球抽样等，由 ５ 个节点构成的能源供应链中 ｎ ＝ ６，其含义是测试边和不存在的边比较了 ６ 次。 而在文中利用计算机程序计算 ＡＵＣ 值时，比较的边 （预测边和不存在边的比较）是随机抽取的，因此即 便 Ｅ Ｐ 中信息完全一样，抽样次数和抽样比较对象不 同导致 ＡＵＣ 值变化，为了使得到的 ＡＵＣ 越接近真 实值，抽样次数 ｎ 越大越好。 ２ 能源供应链网络合作演化分析 本文运用链路预测对能源供应链合作演化进行 研究，将能源供应链网络中节点内外部信息量化，对 量化后的数据进行划分，再利用相似性指标对预测 进行得分，最后使用 ＡＵＣ 评价指标对预测的精确性 进行对比分析。 ２．１ 能源供应链网络结构 一个简单无向无权网络，由点和边构成，需要满 足以下 ４ 个条件： １）节点自身不可以与自身连接； ２）节点间最多只有一条连线，不可出现多条连边； ３）连边不具有方向性； ４）连边只代表节点间关系，代表的是合作的关 系，没有对应的权重。 本文分析的能源供应链由 ２０ 个节点企业构成， 将其分别编号为 １，２，…，２０，其节点链接表示其长 期合作情况，如表 １ 所示。 第 ２ 期 张学龙，等：链路预测下能源供应链网络合作演化机制研究 ·２２３·