.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表 １ 各节点企业合作连接情况 Ｔａｂｌｅ １ Ｃｏｏｐｅｒａｔｉｏｎ ａｎｄ ｃｏｎｎｅｃｔｉｏｎ ｏｆ ｅａｃｈ ｎｏｄｅ ｅｎｔｅｒｐｒｉｓｅ 节点企业编号 合作节点企业编号 １ ２，３，４，５，６，７，８，１１，１４，１６，１７，２０ ２ １，３，４，５，６，７，８，１０，１２，１３，１５，１６，１８，２０ ３ １，２，４，５，６，７，８，１０，１１，１６ ４ １，２，３，５，６，７，８，１１，１４，１６ ５ １，２，３，４，６，７，８，９，１２，１８，１９，２０ ６ １，２，３，４，５，７，８，９，１４ ７ １，２，３，４，５，６，８，９，１０，１２，１４，１５，１９ ８ １，２，３，４，５，６，７，１７ ９ ５，６，７，１０ １０ ２，３，７，９，１３ １１ １，３，４ １２ ２，５，７，１３ １３ ２，１０，１２ １４ １，４，６，７，１９ １５ ２，７ １６ １，２，３，４，１７，１８ １７ １，８，１６ １８ ２，５，１６ １９ ５，７，１４ ２０ １，２，５ 由表 １ 中所示的节点企业的合作情况，将 其合作转化成连边。 在使用计算机分析时，用邻居 矩阵来刻画网络，假设能源供应链网络的邻居矩阵 为 Ａ ，由上表可知 Ａ 是一个 ２０×２０ 的方阵，如果节 点 ｖｘ、ｖｙ 有合作关系，那么 Ａ 的第 ｘ 行 ｙ 列上的元素 就为 １，否则为 ０。 为了方便研究，在满足构建条件 的同时，作出如下假设： １）传统的供应链管理是按照上下游关系将供 应链中企业分为制造商、分销商、零售商等，而本文 研究不考虑企业的类型，只是将企业作为网络中的 一个节点；其次，一般供应链的末端都是消费者，为 了方便统计，将零售商作为整个网络的边界点； ２）企业间有相互的合作关系，则彼此之间存在 一条连线，合作是指长期的合作，短期的或者偶尔的 合作将不作为连线标准，同时认为合作是相互的，不 考虑连边的方向性； ３）将供应链企业合作关系抽象为无向网络，忽 略企业间上下游的关系，默认企业间的传递信息是 对称的，所以没有对边进行赋值。 ２．２ 基于网络结构相似性的指标 利用节点间的相似性进行链路预测时，两个节 点之间相似性越大，它们之间存在链接的可能性就 会越大。 相似性也为一种接近的程度。 基于网络结 构相似性可分为基于局部信息的相似性、基于路径 的相似性和基于随机游走的相似性。 基于局部信息的最简单的相似性指标是共同邻 居的相似性指标 ＣＮ ［２４］ （ｃｏｍｍｏｎ ｎｅｉｇｈｂｏｒｓ），又称为 结构等价（ ｓｔｒｕｃｔｕｒａｌ ｅｑｕｉｖａｌｅｎｃｅ），即两个节点如果 有很多的共同邻居节点，那么这两个节点相似。 在 链路预测中应用 ＣＮ 指标的基本假设是两个未链接 的节点如果有更多的共同邻居，则它们更倾向于连 边。 ＣＮ 指标是对于网络中的节点 ｖｘ ，定义其邻居 集合为 Γ（ｘ） ，则两个节点 ｖｘ 和 ｖｙ 的相似性就定义 为两者共同的邻居数，即 ｓｘｙ ＝ Γ（ｘ） ∩ Γ（ｙ） （２） 局部信息相似性指标除了共同邻居的相似性指 标以外，还有基于偏好连接相似性［２５］ （ ＰＡ） 指标。 偏好连接是指优先连接，即一条新边连接到节点 ｖｘ 的概率正比于该节点的度 ｋｘ 的大小。 新链接节点 ｖｘ 和 ｖｙ 的概率正比于两个节点度的乘积。 由此两个 节点间的偏好连接相似性定义为 ｓｘｙ ＝ ｋｘ × ｋｙ （３） 局部信息的相似性指标的优势就在于计算复杂 度较低，但是由于利用信息有限，预测精度受到了限 制。 周涛等［２６］在共同邻居的基础上考虑三阶路径 的因素，提出了基于局部路径相似性指标 （ ｌｏｃａｌ ｐａｔｈ，ＬＰ）。 其定义为 ｓｘｙ ＝ Ａ ２ ＋ α （Ａ ３ ）ｘｙ （４） 式中： α 为可调参数， Ａ 表示网络的邻接矩阵， （Ａ ３ ）ｘｙ 表示节点 ｖｘ 和 ｖｙ 之间的长度为 ３ 的路径数 目。 当 α ＝ ０ 时，ＬＰ 指标退化为 ＣＮ 指标。 ＣＮ 指标 本质上是考虑了二阶路径数目，当然 ＬＰ 指标也可 以扩展到为更高阶形式，但是当阶数无穷大的时候， ＬＰ 就会相当于考虑网络全部路径的 Ｋａｔｚ 指标［２７］ 。 Ｋａｔｚ 指标考虑了网络的所有路径，其定义为 ｓｘｙ ＝ α Ａｘｙ ＋ α ２ （Ａ ２ ）ｘｙ ＋ α ３ （Ａ ３ ）ｘｙ ＋ … ＋ α ｉ （Ａ ｉ ）ｘｙ （５） 式中： （Ａ ｉ ）ｘｙ 表示连接节点 ｖｘ 和 ｖｙ 之间长度为 ｉ 的 路径数。 由式（５）可知，当可调参数 α 很小时，高阶 路径的贡献也很小，使得 Ｋａｔｚ 指标的预测效果接近 于 ＬＰ 指标。 有相当数量的相似性指标是基于随机游走的， 譬如有重启的随机游走指标［２８］ （Ｒａｎｄｏｍ ｗａｌｋ ｗｉｔｈ ·２２４· 智 能 系 统 学 报 第 １２ 卷