第12卷第2期 智能系统学报 Vol.12 No.2 2017年4月 CAAI Transactions on Intelligent Systems Apr.2017 D0I:10.11992/is.201605003 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20170111.1705.018.html 链路预测下能源供应链网络合作演化机制研究 张学龙，王军进 (桂林电子科技大学商学院，广西桂林541004)】 摘要：应用供应链网络结构或节点的属性信息预测未产生链接的节点企业合作的可能性是链路预测应用供应链 网络合作演化分析的关键，利用链路预测的理论框架和评价方法，借助5种相似性指标对能源供应链网络合作连边 演化进行预测。研究结果表明：当使用供应链网络结构属性作为单一相似性指标时，RW℉指标的预测效果最好；耦 合指标预测精确度要比单独考虑单一指标时有显著提高：RWR指标和Ktz指标耦合效果要优于和CN指标，PA指 标，LP指标耦合效果，且RWR指标在耦合算法中起到主导性作用：与直接建立网络演化模型相比，链路预测在分析 供应链网络合作演化机制上更为有效。 关键词：供应链网络：合作演化：链路预测：网络结构：能源供应链：相似性指标：精确度：耦合 中图分类号：TP391;273文献标志码：A文章编号：1673-4785(2017)02-0221-08 中文引用格式：张学龙，王军进.链路预测下能源供应链网络合作演化机制研究[J].智能系统学报，2017,12(2)：221-228. 英文引用格式：ZHANG Xuelong,WANG Junjin.On the evolution cooperation mechanism of energy supply chain networks under link prediction[J].CAAI transactions on intelligent systems,2017,12(2):221-228. On the evolution cooperation mechanism of energy supply chain networks under link prediction ZHANG Xuelong,WANG Junjin School of Business,Guilin University of Electronic Technology,Guilin 541004,China) Abstract:Using attribute information of a given network structure or nodes of a supply chain to predict the possibili- ty of cooperation with an unlinked enterprise is key to link prediction being applied to supply chain networks.As such,we predicted side-connected evolutions of network cooperation in energy supply chains by utilizing a theoreti- cal framework and evaluation method for link prediction and five similarity indexes.Our results show that when the attribute of the network structure of a supply chain is used as a single similarity index,the predictive effect of the RWR index is the best.Further,the prediction accuracy of the coupling index is remarkably higher than the single index.Here,the coupling effect between the RWR index and the Katz index is superior to the coupling effects be- tween RWR and CN,PA and LP index.Further,the RWR index plays a leading role in the coupling algorithm. Compared with directly setting up a model for network evolution,link prediction is more effective in analyzing the cooperation evolution mechanism of supply chain networks. Keywords:supply chain network;cooperation evolution;link prediction;network structure;energy supply chain; similarity index;accuracy;coupling 预测是所有的科学学科所不能回避的问题。链路预测是数据挖掘的研究方向之一，尤其在计算机 领域早有较深入的研究，其研究思路主要是基于马 收稿日期：2016-05-03.网络出版日期：2017-01-11. 基金项目：国家自然科学基金项目(71662007)：广西哲学社会科学研究尔可夫链和机器学习[1-]。网络中的链路预测是利 课题(15BY016):桂林电子科技大学研究生教育创新计划项 目(2016YJCX61). 用已知的网络节点以及网络结构等信息，预测网络 通信作者：王军进.E-mail:1204703207@qq.com 中尚未产生连边的两个节点之间链接的可能性。这
第 １２ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．２ ２０１７ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０５００３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１７０１１１．１７０５．０１８．ｈｔｍｌ 链路预测下能源供应链网络合作演化机制研究 张学龙，王军进 （桂林电子科技大学 商学院，广西 桂林 ５４１００４） 摘 要：应用供应链网络结构或节点的属性信息预测未产生链接的节点企业合作的可能性是链路预测应用供应链 网络合作演化分析的关键，利用链路预测的理论框架和评价方法，借助 ５ 种相似性指标对能源供应链网络合作连边 演化进行预测。 研究结果表明：当使用供应链网络结构属性作为单一相似性指标时，ＲＷＲ 指标的预测效果最好；耦 合指标预测精确度要比单独考虑单一指标时有显著提高；ＲＷＲ 指标和 Ｋａｔｚ 指标耦合效果要优于和 ＣＮ 指标、ＰＡ 指 标、ＬＰ 指标耦合效果，且 ＲＷＲ 指标在耦合算法中起到主导性作用；与直接建立网络演化模型相比，链路预测在分析 供应链网络合作演化机制上更为有效。 关键词：供应链网络；合作演化；链路预测；网络结构；能源供应链；相似性指标；精确度；耦合 中图分类号： ＴＰ３９１；Ｆ２７３ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０２－０２２１－０８ 中文引用格式：张学龙，王军进． 链路预测下能源供应链网络合作演化机制研究［Ｊ］． 智能系统学报， ２０１７， １２（２）： ２２１－２２８． 英文引用格式：ＺＨＡＮＧ Ｘｕｅｌｏｎｇ， ＷＡＮＧ Ｊｕｎｊｉｎ． Ｏｎ ｔｈｅ ｅｖｏｌｕｔｉｏｎ ｃｏｏｐｅｒａｔｉｏｎ ｍｅｃｈａｎｉｓｍ ｏｆ ｅｎｅｒｇｙ ｓｕｐｐｌｙ ｃｈａｉｎ ｎｅｔｗｏｒｋｓ ｕｎｄｅｒ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（２）： ２２１－２２８． Ｏｎ ｔｈｅ ｅｖｏｌｕｔｉｏｎ ｃｏｏｐｅｒａｔｉｏｎ ｍｅｃｈａｎｉｓｍ ｏｆ ｅｎｅｒｇｙ ｓｕｐｐｌｙ ｃｈａｉｎ ｎｅｔｗｏｒｋｓ ｕｎｄｅｒ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ＺＨＡＮＧ Ｘｕｅｌｏｎｇ， ＷＡＮＧ Ｊｕｎｊｉｎ （Ｓｃｈｏｏｌ ｏｆ Ｂｕｓｉｎｅｓｓ， Ｇｕｉｌｉｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ， Ｇｕｉｌｉｎ ５４１００４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｕｓｉｎｇ ａｔｔｒｉｂｕｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ａ ｇｉｖｅｎ ｎｅｔｗｏｒｋ ｓｔｒｕｃｔｕｒｅ ｏｒ ｎｏｄｅｓ ｏｆ ａ ｓｕｐｐｌｙ ｃｈａｉｎ ｔｏ ｐｒｅｄｉｃｔ ｔｈｅ ｐｏｓｓｉｂｉｌｉ⁃ ｔｙ ｏｆ ｃｏｏｐｅｒａｔｉｏｎ ｗｉｔｈ ａｎ ｕｎｌｉｎｋｅｄ ｅｎｔｅｒｐｒｉｓｅ ｉｓ ｋｅｙ ｔｏ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｂｅｉｎｇ ａｐｐｌｉｅｄ ｔｏ ｓｕｐｐｌｙ ｃｈａｉｎ ｎｅｔｗｏｒｋｓ． Ａｓ ｓｕｃｈ， ｗｅ ｐｒｅｄｉｃｔｅｄ ｓｉｄｅ⁃ｃｏｎｎｅｃｔｅｄ ｅｖｏｌｕｔｉｏｎｓ ｏｆ ｎｅｔｗｏｒｋ ｃｏｏｐｅｒａｔｉｏｎ ｉｎ ｅｎｅｒｇｙ ｓｕｐｐｌｙ ｃｈａｉｎｓ ｂｙ ｕｔｉｌｉｚｉｎｇ ａ ｔｈｅｏｒｅｔｉ⁃ ｃａｌ ｆｒａｍｅｗｏｒｋ ａｎｄ ｅｖａｌｕａｔｉｏｎ ｍｅｔｈｏｄ ｆｏｒ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ａｎｄ ｆｉｖｅ ｓｉｍｉｌａｒｉｔｙ ｉｎｄｅｘｅｓ． Ｏｕｒ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｗｈｅｎ ｔｈｅ ａｔｔｒｉｂｕｔｅ ｏｆ ｔｈｅ ｎｅｔｗｏｒｋ ｓｔｒｕｃｔｕｒｅ ｏｆ ａ ｓｕｐｐｌｙ ｃｈａｉｎ ｉｓ ｕｓｅｄ ａｓ ａ ｓｉｎｇｌｅ ｓｉｍｉｌａｒｉｔｙ ｉｎｄｅｘ， ｔｈｅ ｐｒｅｄｉｃｔｉｖｅ ｅｆｆｅｃｔ ｏｆ ｔｈｅ ＲＷＲ ｉｎｄｅｘ ｉｓ ｔｈｅ ｂｅｓｔ． Ｆｕｒｔｈｅｒ， ｔｈｅ ｐｒｅｄｉｃｔｉｏｎ ａｃｃｕｒａｃｙ ｏｆ ｔｈｅ ｃｏｕｐｌｉｎｇ ｉｎｄｅｘ ｉｓ ｒｅｍａｒｋａｂｌｙ ｈｉｇｈｅｒ ｔｈａｎ ｔｈｅ ｓｉｎｇｌｅ ｉｎｄｅｘ． Ｈｅｒｅ， ｔｈｅ ｃｏｕｐｌｉｎｇ ｅｆｆｅｃｔ ｂｅｔｗｅｅｎ ｔｈｅ ＲＷＲ ｉｎｄｅｘ ａｎｄ ｔｈｅ Ｋａｔｚ ｉｎｄｅｘ ｉｓ ｓｕｐｅｒｉｏｒ ｔｏ ｔｈｅ ｃｏｕｐｌｉｎｇ ｅｆｆｅｃｔｓ ｂｅ⁃ ｔｗｅｅｎ ＲＷＲ ａｎｄ ＣＮ， ＰＡ ａｎｄ ＬＰ ｉｎｄｅｘ． Ｆｕｒｔｈｅｒ， ｔｈｅ ＲＷＲ ｉｎｄｅｘ ｐｌａｙｓ ａ ｌｅａｄｉｎｇ ｒｏｌｅ ｉｎ ｔｈｅ ｃｏｕｐｌｉｎｇ ａｌｇｏｒｉｔｈｍ． Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｄｉｒｅｃｔｌｙ ｓｅｔｔｉｎｇ ｕｐ ａ ｍｏｄｅｌ ｆｏｒ ｎｅｔｗｏｒｋ ｅｖｏｌｕｔｉｏｎ， ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｉｓ ｍｏｒｅ ｅｆｆｅｃｔｉｖｅ ｉｎ ａｎａｌｙｚｉｎｇ ｔｈｅ ｃｏｏｐｅｒａｔｉｏｎ ｅｖｏｌｕｔｉｏｎ ｍｅｃｈａｎｉｓｍ ｏｆ ｓｕｐｐｌｙ ｃｈａｉｎ ｎｅｔｗｏｒｋｓ． Ｋｅｙｗｏｒｄｓ： ｓｕｐｐｌｙ ｃｈａｉｎ ｎｅｔｗｏｒｋ； ｃｏｏｐｅｒａｔｉｏｎ ｅｖｏｌｕｔｉｏｎ； ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ； ｎｅｔｗｏｒｋ ｓｔｒｕｃｔｕｒｅ； ｅｎｅｒｇｙ ｓｕｐｐｌｙ ｃｈａｉｎ； ｓｉｍｉｌａｒｉｔｙ ｉｎｄｅｘ； ａｃｃｕｒａｃｙ； ｃｏｕｐｌｉｎｇ 收稿日期：２０１６－０５－０３． 网络出版日期：２０１７－０１－１１． 基金项目：国家自然科学基金项目（７１６６２００７）；广西哲学社会科学研究 课题（１５ＢＪＹ０１６）；桂林电子科技大学研究生教育创新计划项 目（２０１６ＹＪＣＸ６１）． 通信作者：王军进． Ｅ⁃ｍａｉｌ：１２０４７０３２０７＠ ｑｑ．ｃｏｍ． 预测是所有的科学学科所不能回避的问题。 链 路预测是数据挖掘的研究方向之一，尤其在计算机 领域早有较深入的研究，其研究思路主要是基于马 尔可夫链和机器学习［１－３］ 。 网络中的链路预测是利 用已知的网络节点以及网络结构等信息，预测网络 中尚未产生连边的两个节点之间链接的可能性。 这
.222 智能系统学报 第12卷 种预测包含了对网络中实际上存在但尚未被探测到 相似度的影响因素指标可能会表现不一致，以致难 的链路预测，即“未知链接”预测：也包含了目前不 以辨析哪些才是影响网络演化的主导因素，以及这 存在和应该存在或者未来可能会存在的链路预测， 些主导因素在网络演化过程中分别起到了多大的作 即“未来链接”预测。其中，基于相似性（接近程度） 用，这在一定程度上制约了演化模型的发展。 的链路预测是网络链路预测的主流方法。刻画节点 能源在我国社会发展中具有重要战略地位，能 的相似性有较多方法，最简单直接的就是利用节点 源问题已成为影响经济发展、国家安全等重大战略 的属性，网络中属性相似的节点之间更容易链 性问题。能源供应链是由多流程（能源供应、加工、 接[。应用节点属性进行预测的效果良好，如刘宏 配送等)、多部门（生产部门、运输部门等）、多资源 鲲等[]利用链路预测将结构（共同邻居数目）和节 (人力、物力、技术等)要素构成的开放系统，节点企 点属性（地理位置、人口、GDP和第三产业产值）进 业的协调和合作影响整个供应链的运营效率。自然 行耦合，研究中国城市航空网络演化机制：0· 灾害可导致煤电能源供应链脱节，重要电路供电中 Madadhain等[6)利用网络的拓扑结构信息以及节点 断。能源供应链断链的背后，映射出我国能源供应 的属性建立了一个局部的条件概率模型，应用节点 链各个环节需要进行整体规划，实现相互协调与合 属性进行链路预测：Lin)基于节点的属性定义了节 作。因此，对于现实中的能源供应链的合作演化机 点间的相似性，直接用定义的属性进行链路预测。 制有必要进行深入研究。 虽然应用节点外部信息可得到良好的预测效果，但 随着能源供应链面临的问题越来越多，供应链 很多情况这些信息非常难获取，包括信息是保密的、 上节点企业的内外部环境越来越复杂，很多合作问 真假难辨等，甚至无法获得。相对于节点外部信息 题亟需解决，针对能源供应链合作演化，本文提供了 而言，获取网络内部结构信息较为容易也更加可靠。 一个全新的视角，即利用链路预测研究能源供应链 近几年，内部结构相似性的链路预测方法受到越来 合作演化机制问题。在分析链路预测法和评价指标 越多的关注，包括度分布、集聚性质、社团结构、节点 的基础上，对能源供应链进行实证分析，将供应链似 中心性、节点间的路径长度等[s-ioj。Liben-Nowell 然成网络，在供应链网络中选取5个可以代表能源 等[定义了网络拓扑结构的相似性方法，将相似性 供应链的网络结构相似性指标，通过计算5种相似 性指标的精确度，清晰直观地对各指标预测精确度 指标分为节点和路径，并且分析了多种指标在社会 合作网络中的预测效果。周涛等]用9种相似性 进行辨别，找到最佳的预测指标，并将最佳指标和其 他4种指标耦合，运用耦合指标算法更加精确地预 指标对6种现实网络进行了链路预测，进一步验证 测“未知链接”和“未来链接”，为挖掘能源供应链合 了Liben-Nowell等的研究结果，并且提出了两种精 作演化机制的重要驱动因素模型和公平评价模型优 确度更高的指标：资源分配指标和局部路径指标。 劣提供了可能性，链路预测在分析供应链网络演化 Clauset等[s)分析了利用网络的层次结构进行链路 机制上提供了科学的量化方法。 预测的方法，该方法在具有明显层次结构的网络中 表现较好；Rog©rG等)提出了识别错误链路预测 1 问题描述与评价指标 的方法，同时定义了网络错误连边的概念。 国民生产和生活需要消耗大量的能源，每个节点 利用链路预测方法不仅在各种静态网络结构的 企业协调一致保障着整个供应链的高效运营，一旦供 研究成果众多，从动态角度揭示网络演化的机制、各 应链发生问题，小则导致局部瘫痪，大则引起社会动 种微观因素对网络结构形成的影响成果也较为丰 荡。上游企业（如煤炭、电力企业）和下游企业（如钢 富[1-)。利用链路预测研究网络演化机制最常用 铁企业)不仅是供求关系，同时也是一个整体，节点企 的方法是直接建立演化模型从而预测影响网络演化 业之间相互制约和相互合作。供应链中的合作是相 的因素。例如Barabasi-Albert(BA)【]模型是基于 互合作，不存在方向性，因此可将能源供应链节点企 节点度研究网络优先连接机制，针对某些影响因素 业之间的合作关系描述为一个完整无向网络，节点之 建立对象网络并研究其统计特征，如果分析所得的 间的连线代表企业间合作关系，利用无向网络一些特 统计特征具有和真实网络接近的性质，那么这些影 征和链路预测对其进行合作演化研究。 响因素对网络的结构就有显著影响，即这些因素是 针对任意无向网络G,令N为网络的总节点 网络演化的重要机制，否则认为这些影响因素对网 络结构的影响不显著。但衡量模拟网络与真实网络 数，0为总连边数，则U=N(N-1) ,在实际情境中 2
种预测包含了对网络中实际上存在但尚未被探测到 的链路预测，即“未知链接”预测；也包含了目前不 存在和应该存在或者未来可能会存在的链路预测， 即“未来链接”预测。 其中，基于相似性（接近程度） 的链路预测是网络链路预测的主流方法。 刻画节点 的相似性有较多方法，最简单直接的就是利用节点 的属性， 网 络 中 属 性 相 似 的 节 点 之 间 更 容 易 链 接［４］ 。 应用节点属性进行预测的效果良好，如刘宏 鲲等［５］ 利用链路预测将结构（共同邻居数目）和节 点属性（地理位置、人口、ＧＤＰ 和第三产业产值）进 行耦 合， 研 究 中 国 城 市 航 空 网 络 演 化 机 制； Ｏ ＇ Ｍａｄａｄｈａｉｎ 等［６］利用网络的拓扑结构信息以及节点 的属性建立了一个局部的条件概率模型，应用节点 属性进行链路预测；Ｌｉｎ ［７］基于节点的属性定义了节 点间的相似性，直接用定义的属性进行链路预测。 虽然应用节点外部信息可得到良好的预测效果，但 很多情况这些信息非常难获取，包括信息是保密的、 真假难辨等，甚至无法获得。 相对于节点外部信息 而言，获取网络内部结构信息较为容易也更加可靠。 近几年，内部结构相似性的链路预测方法受到越来 越多的关注，包括度分布、集聚性质、社团结构、节点 中心性、节点间的路径长度等［８－１０］ 。 Ｌｉｂｅｎ⁃Ｎｏｗｅｌｌ 等［１１］定义了网络拓扑结构的相似性方法，将相似性 指标分为节点和路径，并且分析了多种指标在社会 合作网络中的预测效果。 周涛等［１２］ 用 ９ 种相似性 指标对 ６ 种现实网络进行了链路预测，进一步验证 了 Ｌｉｂｅｎ⁃Ｎｏｗｅｌｌ 等的研究结果，并且提出了两种精 确度更高的指标：资源分配指标和局部路径指标。 Ｃｌａｕｓｅｔ 等［１３］分析了利用网络的层次结构进行链路 预测的方法，该方法在具有明显层次结构的网络中 表现较好；Ｒｏｇｅｒ Ｇ 等［１４］ 提出了识别错误链路预测 的方法，同时定义了网络错误连边的概念。 利用链路预测方法不仅在各种静态网络结构的 研究成果众多，从动态角度揭示网络演化的机制、各 种微观因素对网络结构形成的影响成果也较为丰 富［１５－１８］ 。 利用链路预测研究网络演化机制最常用 的方法是直接建立演化模型从而预测影响网络演化 的因素。 例如 Ｂａｒａｂáｓｉ⁃Ａｌｂｅｒｔ （ＢＡ） ［１９］ 模型是基于 节点度研究网络优先连接机制，针对某些影响因素 建立对象网络并研究其统计特征，如果分析所得的 统计特征具有和真实网络接近的性质，那么这些影 响因素对网络的结构就有显著影响，即这些因素是 网络演化的重要机制，否则认为这些影响因素对网 络结构的影响不显著。 但衡量模拟网络与真实网络 相似度的影响因素指标可能会表现不一致，以致难 以辨析哪些才是影响网络演化的主导因素，以及这 些主导因素在网络演化过程中分别起到了多大的作 用，这在一定程度上制约了演化模型的发展。 能源在我国社会发展中具有重要战略地位，能 源问题已成为影响经济发展、国家安全等重大战略 性问题。 能源供应链是由多流程（能源供应、加工、 配送等）、多部门（生产部门、运输部门等）、多资源 （人力、物力、技术等）要素构成的开放系统，节点企 业的协调和合作影响整个供应链的运营效率。 自然 灾害可导致煤电能源供应链脱节，重要电路供电中 断。 能源供应链断链的背后，映射出我国能源供应 链各个环节需要进行整体规划，实现相互协调与合 作。 因此，对于现实中的能源供应链的合作演化机 制有必要进行深入研究。 随着能源供应链面临的问题越来越多，供应链 上节点企业的内外部环境越来越复杂，很多合作问 题亟需解决，针对能源供应链合作演化，本文提供了 一个全新的视角，即利用链路预测研究能源供应链 合作演化机制问题。 在分析链路预测法和评价指标 的基础上，对能源供应链进行实证分析，将供应链似 然成网络，在供应链网络中选取 ５ 个可以代表能源 供应链的网络结构相似性指标，通过计算 ５ 种相似 性指标的精确度，清晰直观地对各指标预测精确度 进行辨别，找到最佳的预测指标，并将最佳指标和其 他 ４ 种指标耦合，运用耦合指标算法更加精确地预 测“未知链接”和“未来链接”，为挖掘能源供应链合 作演化机制的重要驱动因素模型和公平评价模型优 劣提供了可能性，链路预测在分析供应链网络演化 机制上提供了科学的量化方法。 １ 问题描述与评价指标 国民生产和生活需要消耗大量的能源，每个节点 企业协调一致保障着整个供应链的高效运营，一旦供 应链发生问题，小则导致局部瘫痪，大则引起社会动 荡。 上游企业（如煤炭、电力企业）和下游企业（如钢 铁企业）不仅是供求关系，同时也是一个整体，节点企 业之间相互制约和相互合作。 供应链中的合作是相 互合作，不存在方向性，因此可将能源供应链节点企 业之间的合作关系描述为一个完整无向网络，节点之 间的连线代表企业间合作关系，利用无向网络一些特 征和链路预测对其进行合作演化研究。 针对任意无向网络 Ｇ ，令 Ｎ 为网络的总节点 数， Ｕ 为总连边数，则 Ｕ ＝ Ｎ（Ｎ － １） ２ ，在实际情境中 ·２２２· 智 能 系 统 学 报 第 １２ 卷
第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所示
不是每个节点之间都存在链接关系。 根据已知网络 属性，对于给定一种链路预测的算法，为每对没有连 边的节点 ｘ 、 ｙ 赋予一个分数值，该分数值表示一种 节点连边关系的相似性，它与节点间链接概率正相 关，分数值越大，两点链接的可能性就越大。 将所有 未链接的节点对按照该分数值从大到小进行排序， 排序越靠前的节点相互链接的概率越大。 为了测试相似性指标预测的准确性，一般将已 知的连边 Ｅ 分为两个部分：训练集 Ｅ Ｔ 和测试集 Ｅ Ｐ 。 显然， Ｅ ＝ Ｅ Ｔ ∪ Ｅ Ｐ ， Ｅ Ｔ ∩ Ｅ Ｐ ＝ ⌀ 。 在此，将属于 Ｕ 但不属于 Ｅ 的边称为不存在的边，称为 Ｊ ，属于 Ｕ 但 不属于 Ｅ Ｔ 的边为未知边，称为 Ｈ 。 衡量链路预测算法精确度的指标主要有 ＡＵ、 Ｐｒｅｃｉｓｉｏｎ 和 ＲａｎｋｉｎｇＳｃｏｒｅ。 这 ３ 个指标对预测精确 度衡量的侧重点不同，其中 ＡＵＣ 是最常见的一种衡 量指标，它从整体上衡量算法的精确度［２０］ ；Ｐｒｅｃｉｓｉｏｎ 只考虑排在前 Ｌ 位的边是否预测准确［２１］ ；而 Ｒａｎｋ⁃ ｉｎｇＳｃｏｒｅ 则更多考虑了所预测边的排序［２２］ 。 文中选 择的衡量算法精确度的指标为 ＡＵＣ，ＡＵＣ 是在 Ｅ Ｐ 中随机选择一条边的分数值比随机选择的一条不存 在的边的分数值高的概率［２３］ 。 每次随机从 Ｅ Ｐ 中选 一条边，再从 Ｊ 中随机选择一条边，若 Ｅ Ｐ 中选择边 的分数值大于 Ｊ 中选择边的分数，那么就加 １ 分；若 两个分数值相等就加 ０．５ 分；若小于就不加分。 这 样独立比较 ｎ 次，如果有 Ｍ 次 Ｅ Ｐ 中的边分数值大于 Ｊ 分数值，有 Ｚ 次两分数值相等，ＡＵＣ 的计算式如式 （１）所示。 ＡＵＣ ＝ （Ｍ ＋ ０．５Ｚ） ／ ｎ （１） 假设所有分数都是随机产生的，因此 ＡＵＣ ≈ ０．５ ，当 ＡＵＣ ≥ ０．５ 时，大于的程度衡量了算法在多 大程度上比随机选择的方法要精确。 为了进一步说 明 ＡＵＣ 指标的含义，假设由 ５ 个节点构成的能源供 应链网络，其结构图如图 １ 所示。 图 １ ５ 个节点能源供应链网络结构 Ｆｉｇ．１ Ｎｅｔｗｏｒｋ ｓｔｒｕｃｔｕｒｅ ｏｆ ｆｉｖｅ ｎｏｄｅ ｅｎｅｒｇｙ ｓｕｐｐｌｙ ｃｈａｉｎｓ 图 １ 表示一个完整的供应链网络结构，实线表 示训练集，虚线表示测试集。 该网络中包含 ５ 个节 点，该网络在理论上存在的连边数是５×（５－１） ／ ２ ＝ １０，其中 ７ 条是已知的，剩下 ３ 条为不存在的边。 为 了验证链路预测算法的精确性，需要在 ７ 条已知边 中选择部分构成 Ｅ Ｐ ，假如选择边 ｛２，４｝ 和 ｛２，５｝ 作为测试边，如图 １（ ｂ）所示，则剩下的 ５ 条已知边 则构成 Ｅ Ｔ 。 在链路预测方法中，只应用 Ｅ Ｔ 中边的 信息，上述中的 Ｅ Ｐ 中的边仅是随机从已知边中选取 的，若再进行下一次验证精确性选择，则测试边不一 定是 ｛２，４｝ 和 ｛２，５｝ ，而是 Ｅ Ｔ 中的任何边都可能 被选出作为测试边， Ｅ Ｔ 中的边只是暂时被“待定”。 根据链路预测算法得到剩下 ５ 条未知边的得分值分 别为 ｓ２５ ＝ ４， ｓ２４ ＝ ４．５， ｓ１４ ＝ ３．８， ｓ３４ ＝ ４．６， ｓ３５ ＝ ４，那 么在计算 ＡＵＣ 时需将未知边按照其得分排序： ｓ１４ ＜ ｓ２５ ＝ ｓ３５ ＜ ｓ２４ ＜ ｓ３４ ，再根据上述 ＡＵＣ 计算公 式，得 ＡＵＣ ＝ （１＋０．５＋１＋１） ／ （２×３）＝ ０．５８３。 由此可以说明，当选择 Ｅ Ｐ 中的边个数发生变化 时，ＡＵＣ 值会相应地变化，即使 Ｅ Ｐ 完全相同时， ＡＵＣ 值也会不同。 因为 ＡＵＣ 计算公式中的 ｎ 是抽 样次数，抽样方式有多种类型，如随机抽样、逐项遍 历、滚雪球抽样等，由 ５ 个节点构成的能源供应链中 ｎ ＝ ６，其含义是测试边和不存在的边比较了 ６ 次。 而在文中利用计算机程序计算 ＡＵＣ 值时，比较的边 （预测边和不存在边的比较）是随机抽取的，因此即 便 Ｅ Ｐ 中信息完全一样，抽样次数和抽样比较对象不 同导致 ＡＵＣ 值变化，为了使得到的 ＡＵＣ 越接近真 实值，抽样次数 ｎ 越大越好。 ２ 能源供应链网络合作演化分析 本文运用链路预测对能源供应链合作演化进行 研究，将能源供应链网络中节点内外部信息量化，对 量化后的数据进行划分，再利用相似性指标对预测 进行得分，最后使用 ＡＵＣ 评价指标对预测的精确性 进行对比分析。 ２．１ 能源供应链网络结构 一个简单无向无权网络，由点和边构成，需要满 足以下 ４ 个条件： １）节点自身不可以与自身连接； ２）节点间最多只有一条连线，不可出现多条连边； ３）连边不具有方向性； ４）连边只代表节点间关系，代表的是合作的关 系，没有对应的权重。 本文分析的能源供应链由 ２０ 个节点企业构成， 将其分别编号为 １，２，…，２０，其节点链接表示其长 期合作情况，如表 １ 所示。 第 ２ 期 张学龙，等：链路预测下能源供应链网络合作演化机制研究 ·２２３·
.224. 智能系统学报 第12卷 表1各节点企业合作连接情况 2.2基于网络结构相似性的指标 Table 1 Cooperation and connection of each node enterprise 利用节点间的相似性进行链路预测时，两个节 节点企业编号 合作节点企业编号 点之间相似性越大，它们之间存在链接的可能性就 1 2.3,4.5.6.7.8,11.14.16.17.20 会越大。相似性也为一种接近的程度。基于网络结 2 1,3.4.5.6.7.8,10.12.13.15.16.18.20 构相似性可分为基于局部信息的相似性、基于路径 3 1.2.4.5.6,7.8.10.11,16 的相似性和基于随机游走的相似性。 4 1.2,3,5,6,7,8,11,14.16 基于局部信息的最简单的相似性指标是共同邻 5 1.2,3,4.6.7.8.9.12.18.19.20 居的相似性指标CN[2](common neighbors),又称为 1,2,3,4,5,7,8,9,14 结构等价(structural equivalence),即两个节点如果 6 有很多的共同邻居节点，那么这两个节点相似。在 1.2.3.4,5.6.8.9.10.12.14.15.19 链路预测中应用CN指标的基本假设是两个未链接 8 1,2,3,4,5,6,7,17 的节点如果有更多的共同邻居，则它们更倾向于连 9 5.6.7,10 边。CN指标是对于网络中的节点：，定义其邻居 10 2.3.7.9,13 集合为T(x),则两个节点，和，的相似性就定义 11 1.3,4 为两者共同的邻居数，即 12 2.5.7.13 sg=T(x)∩T(y)》 (2) 3 2,10.12 局部信息相似性指标除了共同邻居的相似性指 14 1.4.6.7.19 标以外，还有基于偏好连接相似性)(PA)指标。 15 2.7 偏好连接是指优先连接，即一条新边连接到节点 16 1,2.3.4.17.18 的概率正比于该节点的度k,的大小。新链接节点 17 1.8,16 ”,和，的概率正比于两个节点度的乘积。由此两个 18 2.5,16 节点间的偏好连接相似性定义为 19 5.7,14 Say ks X ky (3) 20 1.2.5 局部信息的相似性指标的优势就在于计算复杂 度较低，但是由于利用信息有限，预测精度受到了限 由表1中所示的节点企业的合作情况，将 制。周涛等2]在共同邻居的基础上考虑三阶路径 其合作转化成连边。在使用计算机分析时，用邻居 的因素，提出了基于局部路径相似性指标(local 矩阵来刻画网络，假设能源供应链网络的邻居矩阵 path,LP)。其定义为 为A,由上表可知A是一个20×20的方阵，如果节 s=A2+a(A3) (4) 点)心，有合作关系，那么A的第x行y列上的元素 式中：α为可调参数，A表示网络的邻接矩阵， 就为1，否则为0。为了方便研究，在满足构建条件 (A3),表示节点，和U,之间的长度为3的路径数 的同时，作出如下假设： 目。当a=O时，LP指标退化为CN指标。CN指标 1)传统的供应链管理是按照上下游关系将供 本质上是考虑了二阶路径数目，当然LP指标也可 应链中企业分为制造商、分销商、零售商等，而本文 以扩展到为更高阶形式，但是当阶数无穷大的时候， 研究不考虑企业的类型，只是将企业作为网络中的 LP就会相当于考虑网络全部路径的Katz指标[27)。 一个节点：其次，一般供应链的末端都是消费者，为 Katz指标考虑了网络的所有路径，其定义为 了方便统计，将零售商作为整个网络的边界点； S=aA,+a2(A2)y+a3(A3)y+…+a(A) 2)企业间有相互的合作关系，则彼此之间存在 (5) 一条连线，合作是指长期的合作，短期的或者偶尔的 式中：(A),表示连接节点和v,之间长度为i的 合作将不作为连线标准，同时认为合作是相互的，不 路径数。由式(5)可知，当可调参数α很小时，高阶 考虑连边的方向性： 路径的贡献也很小，使得Katz指标的预测效果接近 3)将供应链企业合作关系抽象为无向网络，忽 于LP指标。 略企业间上下游的关系，默认企业间的传递信息是 有相当数量的相似性指标是基于随机游走的， 对称的，所以没有对边进行赋值。 譬如有重启的随机游走指标[2](Random walk with
表 １ 各节点企业合作连接情况 Ｔａｂｌｅ １ Ｃｏｏｐｅｒａｔｉｏｎ ａｎｄ ｃｏｎｎｅｃｔｉｏｎ ｏｆ ｅａｃｈ ｎｏｄｅ ｅｎｔｅｒｐｒｉｓｅ 节点企业编号 合作节点企业编号 １ ２，３，４，５，６，７，８，１１，１４，１６，１７，２０ ２ １，３，４，５，６，７，８，１０，１２，１３，１５，１６，１８，２０ ３ １，２，４，５，６，７，８，１０，１１，１６ ４ １，２，３，５，６，７，８，１１，１４，１６ ５ １，２，３，４，６，７，８，９，１２，１８，１９，２０ ６ １，２，３，４，５，７，８，９，１４ ７ １，２，３，４，５，６，８，９，１０，１２，１４，１５，１９ ８ １，２，３，４，５，６，７，１７ ９ ５，６，７，１０ １０ ２，３，７，９，１３ １１ １，３，４ １２ ２，５，７，１３ １３ ２，１０，１２ １４ １，４，６，７，１９ １５ ２，７ １６ １，２，３，４，１７，１８ １７ １，８，１６ １８ ２，５，１６ １９ ５，７，１４ ２０ １，２，５ 由表 １ 中所示的节点企业的合作情况，将 其合作转化成连边。 在使用计算机分析时，用邻居 矩阵来刻画网络，假设能源供应链网络的邻居矩阵 为 Ａ ，由上表可知 Ａ 是一个 ２０×２０ 的方阵，如果节 点 ｖｘ、ｖｙ 有合作关系，那么 Ａ 的第 ｘ 行 ｙ 列上的元素 就为 １，否则为 ０。 为了方便研究，在满足构建条件 的同时，作出如下假设： １）传统的供应链管理是按照上下游关系将供 应链中企业分为制造商、分销商、零售商等，而本文 研究不考虑企业的类型，只是将企业作为网络中的 一个节点；其次，一般供应链的末端都是消费者，为 了方便统计，将零售商作为整个网络的边界点； ２）企业间有相互的合作关系，则彼此之间存在 一条连线，合作是指长期的合作，短期的或者偶尔的 合作将不作为连线标准，同时认为合作是相互的，不 考虑连边的方向性； ３）将供应链企业合作关系抽象为无向网络，忽 略企业间上下游的关系，默认企业间的传递信息是 对称的，所以没有对边进行赋值。 ２．２ 基于网络结构相似性的指标 利用节点间的相似性进行链路预测时，两个节 点之间相似性越大，它们之间存在链接的可能性就 会越大。 相似性也为一种接近的程度。 基于网络结 构相似性可分为基于局部信息的相似性、基于路径 的相似性和基于随机游走的相似性。 基于局部信息的最简单的相似性指标是共同邻 居的相似性指标 ＣＮ ［２４］ （ｃｏｍｍｏｎ ｎｅｉｇｈｂｏｒｓ），又称为 结构等价（ ｓｔｒｕｃｔｕｒａｌ ｅｑｕｉｖａｌｅｎｃｅ），即两个节点如果 有很多的共同邻居节点，那么这两个节点相似。 在 链路预测中应用 ＣＮ 指标的基本假设是两个未链接 的节点如果有更多的共同邻居，则它们更倾向于连 边。 ＣＮ 指标是对于网络中的节点 ｖｘ ，定义其邻居 集合为 Γ（ｘ） ，则两个节点 ｖｘ 和 ｖｙ 的相似性就定义 为两者共同的邻居数，即 ｓｘｙ ＝ Γ（ｘ） ∩ Γ（ｙ） （２） 局部信息相似性指标除了共同邻居的相似性指 标以外，还有基于偏好连接相似性［２５］ （ ＰＡ） 指标。 偏好连接是指优先连接，即一条新边连接到节点 ｖｘ 的概率正比于该节点的度 ｋｘ 的大小。 新链接节点 ｖｘ 和 ｖｙ 的概率正比于两个节点度的乘积。 由此两个 节点间的偏好连接相似性定义为 ｓｘｙ ＝ ｋｘ × ｋｙ （３） 局部信息的相似性指标的优势就在于计算复杂 度较低，但是由于利用信息有限，预测精度受到了限 制。 周涛等［２６］在共同邻居的基础上考虑三阶路径 的因素，提出了基于局部路径相似性指标 （ ｌｏｃａｌ ｐａｔｈ，ＬＰ）。 其定义为 ｓｘｙ ＝ Ａ ２ ＋ α （Ａ ３ ）ｘｙ （４） 式中： α 为可调参数， Ａ 表示网络的邻接矩阵， （Ａ ３ ）ｘｙ 表示节点 ｖｘ 和 ｖｙ 之间的长度为 ３ 的路径数 目。 当 α ＝ ０ 时，ＬＰ 指标退化为 ＣＮ 指标。 ＣＮ 指标 本质上是考虑了二阶路径数目，当然 ＬＰ 指标也可 以扩展到为更高阶形式，但是当阶数无穷大的时候， ＬＰ 就会相当于考虑网络全部路径的 Ｋａｔｚ 指标［２７］ 。 Ｋａｔｚ 指标考虑了网络的所有路径，其定义为 ｓｘｙ ＝ α Ａｘｙ ＋ α ２ （Ａ ２ ）ｘｙ ＋ α ３ （Ａ ３ ）ｘｙ ＋ … ＋ α ｉ （Ａ ｉ ）ｘｙ （５） 式中： （Ａ ｉ ）ｘｙ 表示连接节点 ｖｘ 和 ｖｙ 之间长度为 ｉ 的 路径数。 由式（５）可知，当可调参数 α 很小时，高阶 路径的贡献也很小，使得 Ｋａｔｚ 指标的预测效果接近 于 ＬＰ 指标。 有相当数量的相似性指标是基于随机游走的， 譬如有重启的随机游走指标［２８］ （Ｒａｎｄｏｍ ｗａｌｋ ｗｉｔｈ ·２２４· 智 能 系 统 学 报 第 １２ 卷
第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，分
ｒｅｓｔａｒｔ，ＲＷＲ）。 ＲＷＲ 指标假设随机游走粒子在每 走一步的时候都以一定概率返回初始位置。 设粒子 返回概率为 ρ ， Ｐ 为网络概率返回矩阵， 其元素 Ｐｉｘｙ ＝ａｘｙ ／ ｋｘ 表示节点 ｖｘ 处的粒子下一步到节点 ｖｙ 的概率，如果两者相连 ａｘｙ ＝ １，否则 ａｘｙ ＝ ０。 某粒子 初始时刻在节点 ｖｘ 处，那么 ｔ ＋ １ 时刻该粒子到达网 络每个节点概率向量为 πｘ（ｔ ＋ １） ＝ （１ － ρ）Ｐ Ｔπｘ（ｔ） ＋ ρｅｘ （６） 式中： ｅｘ 表示一个一维列向量且仅有第 ｘ 个元素为 １，其他元素都为 ０。 不难得到式（６）的稳定解为 πｘ ＝ ρ （Ｅ － （１ － ρ）Ｐ Ｔ ） － １ｅｘ （７） 式中： πｘｙ 为节点 ｖｘ 出发的粒子最终有多少概率走 到节点 ｖｙ ，由此定义 ＲＷＲ 相似性为 ｓ ＲＷＲ ｘｙ ＝ πｘｙ ＋ πｙｘ （８） ２．３ 相似性算法精确度分析 表 １ 中所示该能源供应链共 ６６ 条连边，不存在 自环（没有单独的点），而 ２０ 个节点的网络在理论 上的链接边数为 ２０×［（２０－１） ／ ２］ ＝ １９０ 条，当前已 知链接数为 ６６，未知链接数为 １９０－６６ ＝ １２４。 假设 测试集比例为 １０％，训练集则为 ９０％，对测试集和 训练集进行一次性划分，在划分的同时需要保证训 练集的连通性。 测试集中的测试边的数目为 ６６ × １０％≈７，最精确的方法是将所有的测试边和不存在 的边都进行比较，共有比较次数为 ７×１２４ ＝ ８６８ 次， 因为计算机程序代码设计的是随机抽样，为了使得 ＡＵＣ 尽可能接近 真 实 值， 本 文 采 取 抽 样 次 数 为 ２００ ０００次，并进行 ２００ 次独立实验，计算出的 ＡＵＣ 值等于 ２００ ０００ 次抽样 ２００ 次独立实验的平均数。 计算 ＡＵＣ 值 的 过 程 类 似 于 伯 努 利 实 验， ２００ ０００次随机抽样的结果不相互影响，忽略比较得 分相等的情况下，计算 ＡＵＣ 值时得分为 １ 的概率为 ｐ ，则得分为 ０ 的概率为 １ － ｐ 。 如此地进行 ｎ 次抽 样得到的 ＡＵＣ 值为 Ｍ／ ｎ，抽样次数越多 ＡＵＣ 值越 接近 ｐ 。 那么，最佳的抽样次数是能够接受的概率 无限接近于 ｐ 的最小 ｎ 值。 设 ＬＰ 指标和 Ｋａｔｚ 指标 中可调参数 α ＝ ０．００１，ＲＷＲ 指标中的粒子返回概率 ρ ＝ ０．９５，５ 种相似性算法在能源供应链中预测的 ＡＵＣ 值平均值和方差如表 ２ 所示。 由表 ２ 看出，当单独以 ５ 种指标作为相似性算 法时，ＲＷＲ 指标的精确度 ＡＵＣ 为 ０． ７９５ ２ 是最高 的，说明通过 ＲＷＲ 指标进行能源供应链节点企业 合作预测更符合网络特征，对于合作演化的机制具 有较高的精确性，而且平均方差 σ ＝ ０．００７ １，在 ５ 种 指标中也是最小的，意味着 ２００ 组独立实验计算的 ＡＵＣ 值波动幅度最小，提高了实验的准确性和可靠 性；利用路径相似指标的 ＬＰ 指标预测效果好于 Ｋａｔｚ 指标，也就是在该能源供应链网络中考虑局部 路径的效果明显好于考虑全部路径，其中 ＬＰ 指标 预测效果也是 ５ 组指标中精确度第 ２ 的指标；基于 局部信息相似指标的 ＰＡ 指标预测的精确度大于 ＣＮ 指标的精确度，但是 ＰＡ 指标的实验数据方差较 大，也就是再次进行实验时可能导致 ＰＡ 指标平均 精确度值变化较大；ＣＮ 指标预在能源供应链中预 测合作的效果最差，和其他 ４ 个指标相比，精确度之 差相差甚大。 在此特别说明的是，表 ２ 中精确度的 平均值并不是绝对的，也就是说，假如再一次进行 ２００ 组独立实验时，计算的结果可能会发生改变，但 是通过各自方差可知变化浮动不会太大。 表 ２ ５ 种相似性算法预测精确度和方差 Ｔａｂｌｅ ２ Ｔｈｅ ｐｒｅｄｉｃｔｉｏｎ ａｃｃｕｒａｃｙ ａｎｄ ｖａｒｉａｎｃｅ ｏｆ ｆｉｖｅ ｋｉｎｄｓ ｏｆ ｓｉｍｉｌａｒｉｔｙ ａｌｇｏｒｉｔｈｍｓ 算法名称 精确度 方差 共同邻居（ＣＮ） ０．７３７ ４ ０．００９ ３ 偏好连接（ＰＡ） ０．７５９ ３ ０．０１０ ４ 局部路径（ＬＰ） ０．７６０ ３ ０．００９ ０ 全部路径（Ｋａｔｚ） ０．７４６ ５ ０．００９ ５ 重启的随机游走（ＲＷＲ） ０．７９５ ２ ０．００７ １ 为了丰富算法的选择，将 ５ 种指标算法进行相 互结合，以便观察两种指标耦合后预测效果好还是 单独利用相似性指标效果好。 本文设计的是：经过 计算后的精确度最高的 ＲＷＲ 指标与其他 ４ 种指标 分别耦合从而进行链路预测，也就是将基于随机游 走的指标与路径相似性指标、局部信息相似性指标 进行耦合。 采用的是最简单的线性方式，即 ｓ ＝ ｘ × ｓ ＲＷＲ ＋ （１ － ｘ）ｓ ＱＴ （９） 式中： ｓ ＲＷＲ 是基于 ＲＷＲ 指标， ｓ ＱＴ 是基于其他 ４ 种 结构性指标，参数 ｘ ∈ ［０，１］ ，当 ｘ ＝ １ 时，算法回归 到 ｓ ＲＷＲ ，当 ｘ ＝ ０ 时，算法回归到 ｓ ＱＴ 。 式（９）中实际上是对计算机程序中指标算法的 得分进行重新计算，为了统一标准，将每种相似性指 标得分值作归一化处理，即每组数据都除以组别数 据中的最大值。 值得注意的是，所有算法最后的链 接边的得分都是在训练集的基础上计算出来的，也 就是在训练集和测试集划分后，原网络的链接情况 就是去掉测试集中的边剩下训练集的边，测试集中 边和不存在链接一样不存在了，预测的时候只可以 应用训练集中的信息。 参数 ｘ 的区间为 ［０．１，０．９５］ ，步长为 ０．０５，分 第 ２ 期 张学龙，等：链路预测下能源供应链网络合作演化机制研究 ·２２５·
.226 智能系统学报 第12卷 别计算4种耦合指标算法的精确度结果如表3。 0.81 RWR+LP 表3耦合后精确度计算结果 0.80 RWR Table 3 Calculation result of accuracy after coupling 0.79 t RWR+CN RWR+PA RWR+LP RWR+Katz 0.78 0.1 0.7696 0.7675 0.7707 0.7979 0.77 0.15 0.7628 0.7744 0.7770 0.7997 0.76 0.2 0.7581 0.7798 0.7808 0.7978 0.75 0.150.250.350.450.550.650.750.850.95 0.25 0.7557 0.7681 0.7640 0.8014 0.3 0.7626 0.7783 0.7730 0.7901 (c)RWR+LP 0.81 0.35 0.7675 0.7846 0.7806 0.8040 RWR+Katz 0.4 0.7773 0.7744 0.7729 0.7951 ···RWR 0.79 0.45 0.7729 0.7841 0.7777 0.7865 号078 0.5 0.7855 0.7785 0.7754 0.7938 元0.77 0.55 0.7700 0.7823 0.7809 0.7838 0.76 0.6 0.7799 0.7844 0.7825 0.7996 0.75 0.74 0.65 0.7869 0.7883 0.7882 0.7887 0.150.250.350.450.550.650.750.850.95 0.7 0.7840 0.7760 0.7771 0.7915 (d)RWR+Katz 0.75 0.7890 0.7845 0.7834 0.7887 图2耦合算法精确度随着参数的变化情况 0.8 0.7791 0.7898 0.7907 0.7973 Fig.2 The accuracy of coupling algorithms change with 0.85 0.7833 0.8015 0.8028 0.8048 the parameter 0.9 0.7861 0.7904 0.7904 0.8015 对比图2(a)~2(d),可以得出： 0.95 0.8057 0.8007 0.8001 0.7991 1)将RWR指标与其他各4个指标相互耦合后 根据表3数据，确定耦合后算法精确度变化趋 预测能源供应链网络链路合作演化效果总比单独考 势如图2所示。图3展现了4种耦合算法随着参数 虑其他4个指标预测效果要好，同时存在最优参数 x变化，预测精确度的变化情况。 使得耦合指标算法预测精确度要高于单独考虑 0.81 RWR+CN RWR指标。 0.80 ◆RWR 2)观察图2(b)和图2(c)可知，RWR指标分别 0.79 0.78 耦合PA指标、LP指标后精确度变化趋势几乎是相 90.77 同的，在单独考虑PA指标、LP指标时，其精确度就 之0.76 几乎相等，因此可以认为在能源供应链网络链路合 0.75 作预测时，PA指标和LP指标是等价的，预测效果 0.74 ◆◆◆CN 0.73 是相近的。 0.150.250.350.450.550.650.750.850.95 3)当RWR+Katz耦合后，其精确度在单独考虑 RWR指标时的精确度上下波动，而RWR与其他3 (a)RWR+CN 个指标耦合精确度都有随着参数的增大而增大的趋 0.81 RWR+PA 势，也就是说，RWR+Katz耦合效果明显优于RWR 0.80 RWR 0.79 指标与其他3个指标。 为了更为清晰地进一步观察3种耦合算法的预 0.78 测效果，总结表3和图2中数据于表4中。 0.77 从表4预测精度对比得出，耦合算法的最优精 0.76 PA 确度都比5种单独指标精确度要高，但耦合算法只 0.75 0.150.250.350.450.550.650.750.850.95 比利用RWR指标预测的精确度略微提高，分别提 高了1.547%、0.792%、1.300%、1.207%。同时最优 (b)RWR+PA
别计算 ４ 种耦合指标算法的精确度结果如表 ３。 表 ３ 耦合后精确度计算结果 Ｔａｂｌｅ ３ Ｃａｌｃｕｌａｔｉｏｎ ｒｅｓｕｌｔ ｏｆ ａｃｃｕｒａｃｙ ａｆｔｅｒ ｃｏｕｐｌｉｎｇ ｘ ＲＷＲ＋ＣＮ ＲＷＲ＋ＰＡ ＲＷＲ＋ＬＰ ＲＷＲ＋Ｋａｔｚ ０．１ ０．７６９ ６ ０．７６７ ５ ０．７７０ ７ ０．７９７ ９ ０．１５ ０．７６２ ８ ０．７７４ ４ ０．７７７ ０ ０．７９９ ７ ０．２ ０．７５８ １ ０．７７９ ８ ０．７８０ ８ ０．７９７ ８ ０．２５ ０．７５５ ７ ０．７６８ １ ０．７６４ ０ ０．８０１ ４ ０．３ ０．７６２ ６ ０．７７８ ３ ０．７７３ ０ ０．７９０ １ ０．３５ ０．７６７ ５ ０．７８４ ６ ０．７８０ ６ ０．８０４ ０ ０．４ ０．７７７ ３ ０．７７４ ４ ０．７７２ ９ ０．７９５ １ ０．４５ ０．７７２ ９ ０．７８４ １ ０．７７７ ７ ０．７８６ ５ ０．５ ０．７８５ ５ ０．７７８ ５ ０．７７５ ４ ０．７９３ ８ ０．５５ ０．７７０ ０ ０．７８２ ３ ０．７８０ ９ ０．７８３ ８ ０．６ ０．７７９ ９ ０．７８４ ４ ０．７８２ ５ ０．７９９ ６ ０．６５ ０．７８６ ９ ０．７８８ ３ ０．７８８ ２ ０．７８８ ７ ０．７ ０．７８４ ０ ０．７７６ ０ ０．７７７ １ ０．７９１ ５ ０．７５ ０．７８９ ０ ０．７８４ ５ ０．７８３ ４ ０．７８８ ７ ０．８ ０．７７９ １ ０．７８９ ８ ０．７９０ ７ ０．７９７ ３ ０．８５ ０．７８３ ３ ０．８０１ ５ ０．８０２ ８ ０．８０４ ８ ０．９ ０．７８６ １ ０．７９０ ４ ０．７９０ ４ ０．８０１ ５ ０．９５ ０．８０５ ７ ０．８００ ７ ０．８００ １ ０．７９９ １ 根据表 ３ 数据，确定耦合后算法精确度变化趋 势如图 ２ 所示。 图 ３ 展现了 ４ 种耦合算法随着参数 ｘ 变化，预测精确度的变化情况。 （ａ） ＲＷＲ＋ＣＮ （ｂ）ＲＷＲ＋ＰＡ （ｃ） ＲＷＲ＋ＬＰ （ｄ）ＲＷＲ＋Ｋａｔｚ 图 ２ 耦合算法精确度随着参数的变化情况 Ｆｉｇ．２ Ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｃｏｕｐｌｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｃｈａｎｇｅ ｗｉｔｈ ｔｈｅ ｐａｒａｍｅｔｅｒ 对比图 ２（ａ） ～２（ｄ），可以得出： １）将 ＲＷＲ 指标与其他各 ４ 个指标相互耦合后 预测能源供应链网络链路合作演化效果总比单独考 虑其他 ４ 个指标预测效果要好，同时存在最优参数 使得耦合指标算法预测精确度要高于单独考虑 ＲＷＲ 指标。 ２）观察图 ２（ｂ）和图 ２（ｃ）可知，ＲＷＲ 指标分别 耦合 ＰＡ 指标、ＬＰ 指标后精确度变化趋势几乎是相 同的，在单独考虑 ＰＡ 指标、ＬＰ 指标时，其精确度就 几乎相等，因此可以认为在能源供应链网络链路合 作预测时，ＰＡ 指标和 ＬＰ 指标是等价的，预测效果 是相近的。 ３）当 ＲＷＲ＋Ｋａｔｚ 耦合后，其精确度在单独考虑 ＲＷＲ 指标时的精确度上下波动，而 ＲＷＲ 与其他 ３ 个指标耦合精确度都有随着参数的增大而增大的趋 势，也就是说，ＲＷＲ＋Ｋａｔｚ 耦合效果明显优于 ＲＷＲ 指标与其他 ３ 个指标。 为了更为清晰地进一步观察 ３ 种耦合算法的预 测效果，总结表 ３ 和图 ２ 中数据于表 ４ 中。 从表 ４ 预测精度对比得出，耦合算法的最优精 确度都比 ５ 种单独指标精确度要高，但耦合算法只 比利用 ＲＷＲ 指标预测的精确度略微提高，分别提 高了 １．５４７％、０．７９２％、１．３００％、１．２０７％。 同时最优 ·２２６· 智 能 系 统 学 报 第 １２ 卷
第2期 张学龙，等：链路预测下能源供应链网络合作演化机制研究 .227, 参数x·分别为0.95、0.85，说明了RWR指标在耦合 3)RWR指标和Katz指标耦合效果要优于和 算法中起到了决定性作用，对节点企业合作连边产 CN指标、PA指标、LP指标耦合效果； 生了较大的作用。尽管相比RWR指标耦合算法精 4)RWR指标在耦合算法中起到主导性作用，耦 确度提高不是很明显，但是不可以忽略耦合对象指 合对象指标在耦合中则是不可忽略的。 标在耦合算法所起到的作用。 由于链路预测能够计算预测方法的准确度，能 表4耦合算法预测的精确度对比 够清晰直观地利用量化结果对各种因素进行辨别为 Table 4 Accuracy comparison of prediction by coupling al- 供应链网络合作演化机制研究提供了分析工具和全 gorithms 新的视角，推动复杂网络演化模型的理论研究。 提高率/%提高率/% 为开拓链路预测，针对供应链网络结构的研究视 耦合算法 最优参数精确度（与RWR(与耦合 角，增加供应链网络结构属性：将结构属性与外部属 相比) 对象相比) 性相耦合等方面将是进一步研究内容，使得后续供应 RWR+CN 0.95 0.8075 1.547 9.506 链网络合作演化机制研究更加全面和更具有深度。 RWR+PA 0.85 0.8015 0.792 5.558 参考文献： RWR+LP 0.85 0.8082 1.300 6.300 RWR+Katz 0.85 0.8048 1.207 7.810 [1]SARUKKAI RR.Link prediction and path analysis using Markov chains[J].Computer networks,2000,33(1/2/3/ 相比单独考虑其他4种指标，预测精确度分别 4/5/6)：377-386. 提高了9.506%、5.558%、6.300%、7.810%，有显著提 [2]ZHU Jianhan,HONG Jun,HUGHES J G.Using Markov 高。耦合算法提高了耦合中原本精确度较小的指标 chains for link prediction in adaptive web sites[M]//BUS- 预测的效果，其中帮助CN提高了接近10%的精确 TARD D.LIU Weiru,STERRITT R.Soft-Ware 2002: 度，说明了耦合算法达到了提高指标在能源供应链 Computing in An Imperfect World.Berlin Heidelberg: 网络中预测合作连边的目的，也为链路预测中各类 Springer,.2002:60-73. 指标结合提高了可能性。 [3]POPESCUL A,UNGAR L H.Statistical relational learning 上述研究结论并不说明CN指标在能源供应链 for link prediction[C]//Proceedings of Workshop on Learn- 网络预测合作连边中不重要，文献[12]比较了9种 ing Statistical Models from Relational Data.New York: 基于共同邻居的局部接近性算法，结果显示CN指 ACM Press,2003:81-87. 标表现较好，而且对航空网络的预测比较准确，AUC [4]KOLACZYK EE.Some implications of path-based sampling on the Internet[C]//Proceedings of a Workshop on Statis- 可达到0.9以上。本文是应用链路预测方法研究能 tics of Networks.Washington:National Academies Press, 源供应链网络中节点企业合作演化机制，由于计算 2007:207-226. 程序中的随机性，因此各指标精确度对所有供应链 [5]刘宏鲲，吕琳媛，周涛.利用链路预测推断网络演化机 网络预测不可一概而论。 制[J刀].中国科学：物理学力学天文学，2011,41(7)： 3结论 816-823. LIU Hongkun,LYU Linyuan,ZHOU Tao.Uncovering the 能源供应链的合作问题凸显出合作演化机制研 network evolution mechanism by link prediction[]].Scientia 究的重要性，一般研究能源供应链网络合作演化机 sinica:physica,mechanica astronomica,2011,41(7): 制的常用方法直接应用演化模型来推测影响供应链 816-823 网络合作演化的因素，但由于可比较的结构特征量 [6]0'MADADHAIN J,HUTCHINS J,SMYTH P.Prediction 太多，不同的模型之间难以进行定量地比较，而链路 and ranking algorithms for event-based network data[J]. 预测方法推测网络演化的机制规避了传统方法的缺 ACM SIGKDD explorations newsletter,2005,7(2):23- 30 陷。本文应用基于网络结构的链路预测方法，研究 [7]LIN Dekang.An information-theoretic definition of Similarity 能源供应链网络合作演化机制，研究结果表明： [C]//Proceedings of the Fifteenth International Conference 1)在5种相似性指标中，RWR指标预测供应链 on Machine Learning.San Francisco:Morgan Kaufmann 网络合作的效果最好； Publishers,1998:296-304. 2)耦合其他4种指标时，耦合后的预测效果会 [8]吕琳媛.复杂网络链路预测[J].电子科技大学学报， 优于单独考虑时，达到了耦合指标的目的； 2010,39(5):651-661
参数 ｘ ∗ 分别为 ０．９５、０．８５，说明了 ＲＷＲ 指标在耦合 算法中起到了决定性作用，对节点企业合作连边产 生了较大的作用。 尽管相比 ＲＷＲ 指标耦合算法精 确度提高不是很明显，但是不可以忽略耦合对象指 标在耦合算法所起到的作用。 表 ４ 耦合算法预测的精确度对比 Ｔａｂｌｅ ４ Ａｃｃｕｒａｃｙ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｐｒｅｄｉｃｔｉｏｎ ｂｙ ｃｏｕｐｌｉｎｇ ａｌ⁃ ｇｏｒｉｔｈｍｓ 耦合算法 最优参数 精确度 提高率／ ％ （与 ＲＷＲ 相比） 提高率／ ％ （与耦合 对象相比） ＲＷＲ＋ＣＮ ０．９５ ０．８０７ ５ １．５４７ ９．５０６ ＲＷＲ＋ＰＡ ０．８５ ０．８０１ ５ ０．７９２ ５．５５８ ＲＷＲ＋ＬＰ ０．８５ ０．８０８ ２ １．３００ ６．３００ ＲＷＲ＋Ｋａｔｚ ０．８５ ０．８０４ ８ １．２０７ ７．８１０ 相比单独考虑其他 ４ 种指标，预测精确度分别 提高了 ９．５０６％、５．５５８％、６．３００％、７．８１０％，有显著提 高。 耦合算法提高了耦合中原本精确度较小的指标 预测的效果，其中帮助 ＣＮ 提高了接近 １０％的精确 度，说明了耦合算法达到了提高指标在能源供应链 网络中预测合作连边的目的，也为链路预测中各类 指标结合提高了可能性。 上述研究结论并不说明 ＣＮ 指标在能源供应链 网络预测合作连边中不重要，文献［１２］比较了 ９ 种 基于共同邻居的局部接近性算法，结果显示 ＣＮ 指 标表现较好，而且对航空网络的预测比较准确，ＡＵＣ 可达到 ０．９ 以上。 本文是应用链路预测方法研究能 源供应链网络中节点企业合作演化机制，由于计算 程序中的随机性，因此各指标精确度对所有供应链 网络预测不可一概而论。 ３ 结论 能源供应链的合作问题凸显出合作演化机制研 究的重要性，一般研究能源供应链网络合作演化机 制的常用方法直接应用演化模型来推测影响供应链 网络合作演化的因素，但由于可比较的结构特征量 太多，不同的模型之间难以进行定量地比较，而链路 预测方法推测网络演化的机制规避了传统方法的缺 陷。 本文应用基于网络结构的链路预测方法，研究 能源供应链网络合作演化机制，研究结果表明： １）在 ５ 种相似性指标中，ＲＷＲ 指标预测供应链 网络合作的效果最好； ２）耦合其他 ４ 种指标时，耦合后的预测效果会 优于单独考虑时，达到了耦合指标的目的； ３） ＲＷＲ 指标和 Ｋａｔｚ 指标耦合效果要优于和 ＣＮ 指标、ＰＡ 指标、ＬＰ 指标耦合效果； ４）ＲＷＲ 指标在耦合算法中起到主导性作用，耦 合对象指标在耦合中则是不可忽略的。 由于链路预测能够计算预测方法的准确度，能 够清晰直观地利用量化结果对各种因素进行辨别为 供应链网络合作演化机制研究提供了分析工具和全 新的视角，推动复杂网络演化模型的理论研究。 为开拓链路预测，针对供应链网络结构的研究视 角，增加供应链网络结构属性；将结构属性与外部属 性相耦合等方面将是进一步研究内容，使得后续供应 链网络合作演化机制研究更加全面和更具有深度。 参考文献： ［１］ ＳＡＲＵＫＫＡＩ Ｒ Ｒ． Ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ａｎｄ ｐａｔｈ ａｎａｌｙｓｉｓ ｕｓｉｎｇ Ｍａｒｋｏｖ ｃｈａｉｎｓ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｎｅｔｗｏｒｋｓ， ２０００， ３３（１ ／ ２ ／ ３ ／ ４ ／ ５ ／ ６）： ３７７－３８６． ［２］ ＺＨＵ Ｊｉａｎｈａｎ， ＨＯＮＧ Ｊｕｎ， ＨＵＧＨＥＳ Ｊ Ｇ． Ｕｓｉｎｇ Ｍａｒｋｏｖ ｃｈａｉｎｓ ｆｏｒ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｉｎ ａｄａｐｔｉｖｅ ｗｅｂ ｓｉｔｅｓ［Ｍ］ ／ ／ ＢＵＳ⁃ ＴＡＲＤ Ｄ， ＬＩＵ Ｗｅｉｒｕ， ＳＴＥＲＲＩＴＴ Ｒ． Ｓｏｆｔ⁃Ｗａｒｅ ２００２： Ｃｏｍｐｕｔｉｎｇ ｉｎ Ａｎ Ｉｍｐｅｒｆｅｃｔ Ｗｏｒｌｄ． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２００２： ６０－７３． ［３］ＰＯＰＥＳＣＵＬ Ａ， ＵＮＧＡＲ Ｌ Ｈ． Ｓｔａｔｉｓｔｉｃａｌ ｒｅｌａｔｉｏｎａｌ ｌｅａｒｎｉｎｇ ｆｏｒ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｗｏｒｋｓｈｏｐ ｏｎ Ｌｅａｒｎ⁃ ｉｎｇ Ｓｔａｔｉｓｔｉｃａｌ Ｍｏｄｅｌｓ ｆｒｏｍ Ｒｅｌａｔｉｏｎａｌ Ｄａｔａ． Ｎｅｗ Ｙｏｒｋ： ＡＣＭ Ｐｒｅｓｓ， ２００３： ８１－８７． ［４］ＫＯＬＡＣＺＹＫ Ｅ Ｅ． Ｓｏｍｅ ｉｍｐｌｉｃａｔｉｏｎｓ ｏｆ ｐａｔｈ⁃ｂａｓｅｄ ｓａｍｐｌｉｎｇ ｏｎ ｔｈｅ Ｉｎｔｅｒｎｅｔ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ａ Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｔａｔｉｓ⁃ ｔｉｃｓ ｏｆ Ｎｅｔｗｏｒｋｓ． Ｗａｓｈｉｎｇｔｏｎ： Ｎａｔｉｏｎａｌ Ａｃａｄｅｍｉｅｓ Ｐｒｅｓｓ， ２００７： ２０７－２２６． ［５］刘宏鲲， 吕琳媛， 周涛． 利用链路预测推断网络演化机 制［Ｊ］． 中国科学： 物理学 力学 天文学， ２０１１， ４１（７）： ８１６－８２３． ＬＩＵ Ｈｏｎｇｋｕｎ， ＬＹＵ Ｌｉｎｙｕａｎ， ＺＨＯＵ Ｔａｏ． Ｕｎｃｏｖｅｒｉｎｇ ｔｈｅ ｎｅｔｗｏｒｋ ｅｖｏｌｕｔｉｏｎ ｍｅｃｈａｎｉｓｍ ｂｙ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ［Ｊ］． Ｓｃｉｅｎｔｉａ ｓｉｎｉｃａ： ｐｈｙｓｉｃａ， ｍｅｃｈａｎｉｃａ ＆ ａｓｔｒｏｎｏｍｉｃａ， ２０１１， ４１（７）： ８１６－８２３． ［６］Ｏ＇ＭＡＤＡＤＨＡＩＮ Ｊ， ＨＵＴＣＨＩＮＳ Ｊ， ＳＭＹＴＨ Ｐ． Ｐｒｅｄｉｃｔｉｏｎ ａｎｄ ｒａｎｋｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｅｖｅｎｔ⁃ｂａｓｅｄ ｎｅｔｗｏｒｋ ｄａｔａ ［ Ｊ］． ＡＣＭ ＳＩＧＫＤＤ ｅｘｐｌｏｒａｔｉｏｎｓ ｎｅｗｓｌｅｔｔｅｒ， ２００５， ７（ ２）： ２３－ ３０． ［７］ＬＩＮ Ｄｅｋａｎｇ． Ａｎ ｉｎｆｏｒｍａｔｉｏｎ⁃ｔｈｅｏｒｅｔｉｃ ｄｅｆｉｎｉｔｉｏｎ ｏｆ Ｓｉｍｉｌａｒｉｔｙ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｆｉｆｔｅｅｎｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ． Ｓａｎ Ｆｒａｎｃｉｓｃｏ： Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ Ｐｕｂｌｉｓｈｅｒｓ， １９９８： ２９６－３０４． ［８］吕琳媛． 复杂网络链路预测［ Ｊ］． 电子科技大学学报， ２０１０， ３９（５）： ６５１－６６１． 第 ２ 期 张学龙，等：链路预测下能源供应链网络合作演化机制研究 ·２２７·
·228 智能系统学报 第12卷 Lu Linyuan.Link prediction on complex networks[.Jour- [20]HANLEY J A,MCNEIL B J.The meaning and use of the nal of university of electronic science and technology of Chi- area under a receiver operating characteristic (ROC)curve na,2010,39(5):651-661. [J].Radiology,1982,143(1):29-36. [9]Lu Linyuan,ZHOU Tao.Link prediction in complex net- [21]HERLOCKER J L,KONSTAN J A,TERVEEN L G,et works:a survey[J].Physica A:statistical mechanics and al.Evaluating collaborative filtering recommender systems its applications,2011,390(6):1150-1170. [J].ACM transactions on information systems,2004,22 [10]GETOOR L,DIEHL C P.Link mining:a survey [J]. (1):5-53. ACM SIGKDD explorations newsletter,2005,7(2):3- [22]ZHOU Tao,REN Jie,MEDO M,et al.Bipartite network 12. projection and personal recommendation[J].Physical re- [11]LIBEN-NOWELL D,KLEINBERG J.The link prediction view E,2007,76(4):046115. problem for social networks[J].Journal of the American [23]FAWCETT T.An introduction to ROC analysis[J].Pattern society for information science and technology,2007,58 recognition letters,2006,27(8):861-874. (7):1019-1031. [24]LORRAIN F,WHITE H C.Structural equivalence of indi- [12]ZHOU Tao,Lu Linyuan,ZHANG Yicheng.Predicting viduals in social networks[J].The journal of mathematical missing links via local information [J].The European s0 ciology,1971,1(1):49-80. physical journal B,2009,71(4):623-630 [25]XIE Yanbo,ZHOU Tao,WANG Binghong.Scale-free net- [13]CLAUSET A,MOORE C,NEWMAN M E J.Hierarchical works without growth[J].Physica A:statistical mechanics structure and the prediction of missing links in networks and its applications,2008,387(7):1683-1688. [J].Nature,2008,453(7191):98-101. [26]Lii Linyuan,JIN Cihang,ZHOU Tao.Similarity index [14]GUIMERa R,SALES-PARDO M.Missing and spurious in- based on local paths for link prediction of complex net- teractions and the reconstruction of complex networks[J]. works[J].Physical review E.2009.80(4):046122. Proceedings of the national academy of sciences of the U. [27]KATZ L.A new status index derived from sociometric anal- nited States of America,2009,106(52):22073-22078. ysis[J].Psychometrika,1953,18(1):39-43. [15]ADAMIC L A,HUBERMAN B A.Power-law distribution [28]BRIN S,PAGE L.The anatomy of a large-scale hypertex- of the world wide web[J].Science,2000,287(5461): tual Web search engine[J].Computer networks and ISDN 2115. systems,1998,30(1):107-117. [16]NEWMAN M E J.The structure of scientific collaboration 作者简介： networks[J].Proceedings of the national academy of sci- 张学龙.男，1978年生，副教授.博 ences of the United States of America.2001,98(2):404 士，主要研究方向为供应链管理、工业 -409. 工程，决策分析。 [17]ALBERT R,BARABGSI A L.Statistical mechanics of complex networks[J].Reviews of modern physics,2002, 74(1):47-97. [18]DOROGOVTSEV S N,MENDES J FF.Evolution of net- 王军进，男，1990年生，硕士研究 works[J].Advances in physics,2002,51(4):1079- 生，主要研究方向为供应链管理。 1187. [19]BARABOSI A L,Albert R.Emergence of scaling in ran- dom networks[J].Science,1999,286(5439):509-512
Ｌü Ｌｉｎｙｕａｎ． Ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｏｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｊｏｕｒ⁃ ｎａｌ ｏｆ ｕｎｉｖｅｒｓｉｔｙ ｏｆ ｅｌｅｃｔｒｏｎｉｃ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｃｈｉ⁃ ｎａ， ２０１０， ３９（５）： ６５１－６６１． ［９］ Ｌü Ｌｉｎｙｕａｎ， ＺＨＯＵ Ｔａｏ． Ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔ⁃ ｗｏｒｋｓ： ａ ｓｕｒｖｅｙ［ Ｊ］． Ｐｈｙｓｉｃａ Ａ： ｓｔａｔｉｓｔｉｃａｌ ｍｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１１， ３９０（６）： １１５０－１１７０． ［１０］ ＧＥＴＯＯＲ Ｌ， ＤＩＥＨＬ Ｃ Ｐ． Ｌｉｎｋ ｍｉｎｉｎｇ： ａ ｓｕｒｖｅｙ ［ Ｊ］． ＡＣＭ ＳＩＧＫＤＤ ｅｘｐｌｏｒａｔｉｏｎｓ ｎｅｗｓｌｅｔｔｅｒ， ２００５， ７（２）： ３－ １２． ［１１］ＬＩＢＥＮ⁃ＮＯＷＥＬＬ Ｄ， ＫＬＥＩＮＢＥＲＧ Ｊ． Ｔｈｅ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｐｒｏｂｌｅｍ ｆｏｒ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ａｍｅｒｉｃａｎ ｓｏｃｉｅｔｙ ｆｏｒ ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ， ２００７， ５８ （７）： １０１９－１０３１． ［１２］ ＺＨＯＵ Ｔａｏ， Ｌü Ｌｉｎｙｕａｎ， ＺＨＡＮＧ Ｙｉｃｈｅｎｇ． Ｐｒｅｄｉｃｔｉｎｇ ｍｉｓｓｉｎｇ ｌｉｎｋｓ ｖｉａ ｌｏｃａｌ ｉｎｆｏｒｍａｔｉｏｎ ［ Ｊ ］． Ｔｈｅ Ｅｕｒｏｐｅａｎ ｐｈｙｓｉｃａｌ ｊｏｕｒｎａｌ Ｂ， ２００９， ７１（４）： ６２３－６３０． ［１３］ＣＬＡＵＳＥＴ Ａ， ＭＯＯＲＥ Ｃ， ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｈｉｅｒａｒｃｈｉｃａｌ ｓｔｒｕｃｔｕｒｅ ａｎｄ ｔｈｅ ｐｒｅｄｉｃｔｉｏｎ ｏｆ ｍｉｓｓｉｎｇ ｌｉｎｋｓ ｉｎ ｎｅｔｗｏｒｋｓ ［Ｊ］． Ｎａｔｕｒｅ， ２００８， ４５３（７１９１）： ９８－１０１． ［１４］ＧＵＩＭＥＲà Ｒ， ＳＡＬＥＳ⁃ＰＡＲＤＯ Ｍ． Ｍｉｓｓｉｎｇ ａｎｄ ｓｐｕｒｉｏｕｓ ｉｎ⁃ ｔｅｒａｃｔｉｏｎｓ ａｎｄ ｔｈｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｎａｔｉｏｎａｌ ａｃａｄｅｍｙ ｏｆ ｓｃｉｅｎｃｅｓ ｏｆ ｔｈｅ Ｕ⁃ ｎｉｔｅｄ Ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ， ２００９， １０６（５２）： ２２０７３－２２０７８． ［１５］ＡＤＡＭＩＣ Ｌ Ａ， ＨＵＢＥＲＭＡＮ Ｂ Ａ． Ｐｏｗｅｒ⁃ｌａｗ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｔｈｅ ｗｏｒｌｄ ｗｉｄｅ ｗｅｂ［ Ｊ］． Ｓｃｉｅｎｃｅ， ２０００， ２８７（ ５４６１）： ２１１５． ［１６］ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｔｈｅ ｓｔｒｕｃｔｕｒｅ ｏｆ ｓｃｉｅｎｔｉｆｉｃ ｃｏｌｌａｂｏｒａｔｉｏｎ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｎａｔｉｏｎａｌ ａｃａｄｅｍｙ ｏｆ ｓｃｉ⁃ ｅｎｃｅｓ ｏｆ ｔｈｅ Ｕｎｉｔｅｄ Ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ， ２００１， ９８（２）： ４０４ －４０９． ［１７］ ＡＬＢＥＲＴ Ｒ， ＢＡＲＡＢáＳＩ Ａ Ｌ． Ｓｔａｔｉｓｔｉｃａｌ ｍｅｃｈａｎｉｃｓ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｒｅｖｉｅｗｓ ｏｆ ｍｏｄｅｒｎ ｐｈｙｓｉｃｓ， ２００２， ７４（１）： ４７－９７． ［１８］ＤＯＲＯＧＯＶＴＳＥＶ Ｓ Ｎ， ＭＥＮＤＥＳ Ｊ Ｆ Ｆ． Ｅｖｏｌｕｔｉｏｎ ｏｆ ｎｅｔ⁃ ｗｏｒｋｓ［ Ｊ］． Ａｄｖａｎｃｅｓ ｉｎ ｐｈｙｓｉｃｓ， ２００２， ５１ （ ４）： １０７９ － １１８７． ［１９］ＢＡＲＡＢáＳＩ Ａ Ｌ， Ａｌｂｅｒｔ Ｒ． Ｅｍｅｒｇｅｎｃｅ ｏｆ ｓｃａｌｉｎｇ ｉｎ ｒａｎ⁃ ｄｏｍ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｓｃｉｅｎｃｅ， １９９９， ２８６（５４３９）： ５０９－５１２． ［２０］ＨＡＮＬＥＹ Ｊ Ａ， ＭＣＮＥＩＬ Ｂ Ｊ． Ｔｈｅ ｍｅａｎｉｎｇ ａｎｄ ｕｓｅ ｏｆ ｔｈｅ ａｒｅａ ｕｎｄｅｒ ａ ｒｅｃｅｉｖｅｒ ｏｐｅｒａｔｉｎｇ ｃｈａｒａｃｔｅｒｉｓｔｉｃ （ＲＯＣ） ｃｕｒｖｅ ［Ｊ］． Ｒａｄｉｏｌｏｇｙ， １９８２， １４３（１）： ２９－３６． ［２１］ ＨＥＲＬＯＣＫＥＲ Ｊ Ｌ， ＫＯＮＳＴＡＮ Ｊ Ａ， ＴＥＲＶＥＥＮ Ｌ Ｇ， ｅｔ ａｌ． Ｅｖａｌｕａｔｉｎｇ ｃｏｌｌａｂｏｒａｔｉｖｅ ｆｉｌｔｅｒｉｎｇ ｒｅｃｏｍｍｅｎｄｅｒ ｓｙｓｔｅｍｓ ［Ｊ］． ＡＣＭ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ， ２００４， ２２ （１）： ５－５３． ［２２］ＺＨＯＵ Ｔａｏ， ＲＥＮ Ｊｉｅ， ＭＥＤＯ Ｍ， ｅｔ ａｌ． Ｂｉｐａｒｔｉｔｅ ｎｅｔｗｏｒｋ ｐｒｏｊｅｃｔｉｏｎ ａｎｄ ｐｅｒｓｏｎａｌ ｒｅｃｏｍｍｅｎｄａｔｉｏｎ［ Ｊ］． Ｐｈｙｓｉｃａｌ ｒｅ⁃ ｖｉｅｗ Ｅ， ２００７， ７６（４）： ０４６１１５． ［２３］ＦＡＷＣＥＴＴ Ｔ． Ａｎ ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ ＲＯＣ ａｎａｌｙｓｉｓ［Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ ｌｅｔｔｅｒｓ， ２００６， ２７（８）： ８６１－８７４． ［２４］ＬＯＲＲＡＩＮ Ｆ， ＷＨＩＴＥ Ｈ Ｃ． Ｓｔｒｕｃｔｕｒａｌ ｅｑｕｉｖａｌｅｎｃｅ ｏｆ ｉｎｄｉ⁃ ｖｉｄｕａｌｓ ｉｎ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｔｈｅ ｊｏｕｒｎａｌ ｏｆ ｍａｔｈｅｍａｔｉｃａｌ ｓｏｃｉｏｌｏｇｙ， １９７１， １（１）： ４９－８０． ［２５］ＸＩＥ Ｙａｎｂｏ， ＺＨＯＵ Ｔａｏ， ＷＡＮＧ Ｂｉｎｇｈｏｎｇ． Ｓｃａｌｅ⁃ｆｒｅｅ ｎｅｔ⁃ ｗｏｒｋｓ ｗｉｔｈｏｕｔ ｇｒｏｗｔｈ［Ｊ］． Ｐｈｙｓｉｃａ Ａ： ｓｔａｔｉｓｔｉｃａｌ ｍｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎｓ， ２００８， ３８７（７）： １６８３－１６８８． ［２６］ Ｌü Ｌｉｎｙｕａｎ， ＪＩＮ Ｃｉｈａｎｇ， ＺＨＯＵ Ｔａｏ． Ｓｉｍｉｌａｒｉｔｙ ｉｎｄｅｘ ｂａｓｅｄ ｏｎ ｌｏｃａｌ ｐａｔｈｓ ｆｏｒ ｌｉｎｋ ｐｒｅｄｉｃｔｉｏｎ ｏｆ ｃｏｍｐｌｅｘ ｎｅｔ⁃ ｗｏｒｋｓ［Ｊ］． Ｐｈｙｓｉｃａｌ ｒｅｖｉｅｗ Ｅ， ２００９， ８０（４）： ０４６１２２． ［２７］ＫＡＴＺ Ｌ． Ａ ｎｅｗ ｓｔａｔｕｓ ｉｎｄｅｘ ｄｅｒｉｖｅｄ ｆｒｏｍ ｓｏｃｉｏｍｅｔｒｉｃ ａｎａｌ⁃ ｙｓｉｓ［Ｊ］． Ｐｓｙｃｈｏｍｅｔｒｉｋａ， １９５３， １８（１）： ３９－４３． ［２８］ＢＲＩＮ Ｓ， ＰＡＧＥ Ｌ． Ｔｈｅ ａｎａｔｏｍｙ ｏｆ ａ ｌａｒｇｅ⁃ｓｃａｌｅ ｈｙｐｅｒｔｅｘ⁃ ｔｕａｌ Ｗｅｂ ｓｅａｒｃｈ ｅｎｇｉｎｅ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｎｅｔｗｏｒｋｓ ａｎｄ ＩＳＤＮ ｓｙｓｔｅｍｓ， １９９８， ３０（１）： １０７－１１７． 作者简介： 张学龙，男，１９７８ 年生，副教授，博 士，主要研究方向为供应链管理、工业 工程、决策分析。 王军进，男，１９９０ 年生，硕士研究 生，主要研究方向为供应链管理。 ·２２８· 智 能 系 统 学 报 第 １２ 卷