开放科学（资源服务）标志码（OSID）：

0 概述

链路预测是根据网络中的已有节点信息来预测缺失的节点或链路，它是运用微观层面网络演化机制进行预测的重要方法。依据网络特征提取角度的不同，现有链路预测可分为基于相似性、基于极大似然估计、基于概率模型、基于机器学习这4类方法。其中，基于相似性的方法结构较为简单，同时普适性强且效率高。相似性方法是基于节点之间的接近程度（即2个节点连接的概率大小）^[1]所定义，节点相似性可以通过分析节点属性网络拓扑结构信息而得到。但是在实际应用中，节点属性信息往往很难获得，并且信息的可利用率和可靠性都很低^[2]。相比之下，网络拓扑结构信息非常容易获得，并且一系列实证结果也表明其可靠性较高，因此，利用网络拓扑结构信息获取相似性被研究人员广泛认同^[3]，对于一对节点x和y，可以利用网络结构信息计算它们的相似性分数^[4]。

目前，利用网络结构信息判断节点相似性的方法可分为基于局部信息、基于全局信息、基于准局部信息等方法。局部信息是指节点周围有限的网络结构信息，如节点的度大小、节点的最近邻居，因为该类方法在计算相似度时只利用节点的局部拓扑信息而非所有结构信息，所以计算复杂度低，适用于大型网络，但与此同时，该类方法存在的缺陷是准确度不够。这类相似性方法的评估指标主要有CN^[5]、Salton^[6]、Sorensen^[7]、Jaccard^[8]、AA^[9]、RA^[10]、PA^[11]等。利用全局信息的方法考虑整个网络的拓扑结构信息，使得链路预测更为灵活和准确，但同时提高了时间复杂度，处理大型网络时效率较低。这类相似性方法的评估指标主要有Katz^[12]、ACT^[13]、RWR^[14]、Cos+^[15]等。基于准局部信息的方法通过多跳路径或局部随机游走的方式，在局部信息的基础上引入更多的拓扑信息，相比于全局方法，其计算复杂度较低，而相比于局部方法，其准确度有所提升，该类方法综合了局部方法和全局方法的优势。这类相似性方法的评估指标有LP^[16]、L3^[17]等。

基于相似性的链路预测方法仍然不够理想，特别是当面对大型数据集时计算复杂度较高，而面对小型数据集时准确度较低。局部方法受限于精准度，而全局方法又受限于计算复杂度。因此，大量的准局部方法被提出，它们结合局部方法和全局方法的优势来实现计算复杂度和精准度的均衡。

RSP^[18]指标可以度量路径与资源接收过程的交互关系，每个节点获得一定的初始资源，然后路径上的中间节点可以从它们的邻居接收资源。大量实验结果表明，RSP指标性能表现良好。NCNLC^[19]指标通过结合节点全局归一化共同邻居属性与局部聚类系数来达到平衡全局和局部信息的目的，并将周围邻居节点的连接强度纳入指标的考虑范围。在时序仿真的预测过程中，NCNLC表现出优越的性能，整合了全局和局部指标的优势。通过短路径连接另一个端点的强关系可以带来更强的影响力，而通过长路径连接的强关系只能带来较弱的影响力，基于这一思想，SI被提出^[20]，其通过区分强影响和弱影响来模拟实验的影响。PSI^[21]的目标是通过整合局部路径上的节点信息来提高现有基于路径方法的准确性，它结合了Adamic Adar和Katz这2种应用最广泛的相似度指标的优点，而且性能更优。RA方法利用共同邻居节点进行资源传输分析，但其忽略了共同邻居节点周围的拓扑结构。TT^[22]方法在RA的基础上进行改进，利用资源传输节点的拓扑紧密性，根据节点周围拓扑集聚程度进行量化，并根据传输节点紧密性对共同邻居传输资源量的影响来刻画节点间的相似性。实验结果表明，相比于基准方法，TT方法所得指标的普适性更好，预测准确度更高。受端点之间资源交换的启发，ERA^[23]在RA的基础上进行改进，增加更长的路径并通过参数调整不同网络长路径转移的资源量，节点之间通过区分共同邻居和非共同邻居交互的资源量来衡量相似度。

通过上述分析可以看出，准局部指标能够结合局部指标和全局指标的优势，在计算复杂度较低的情况下达到较高的精准度。受到网络资源分配思想的启发^[24]，通过研究无标度网络中资源流量的动态行为，设定网络中的资源能够自由流动这一动态机制，本文提出一种基于网络资源流量的链路预测方法。为网络设计一种资源流动规则，赋予被预测节点对一定量的资源，使资源自由流动，计算被预测节点对之间的双向流量之和，从而得出相似性分数，其中，流量之和越大，相似性分数越高。该方法通过充分利用节点属性信息、邻域拓扑结构以及路径因素，以提升链路预测的准确度。

1 链路预测相关指标 1.1 相似性指标

相似性指标用来衡量链路预测方法的准确性，以及判断链路存在的可能性。本文给出几种常见的用于对比预测性能的基础指标，包括局部、准局部以及全局指标，分别为CN、Salton、Jaccard、AA、RA、LP、Katz，这7个指标将作为实验部分的对比参照指标，具体信息如下：

1）CN表示2个节点之间共同邻居节点的数目，计算公式如下：

$ {s}_{xy}^{\mathrm{C}\mathrm{N}}=\left|\mathit{\Gamma} \left(x\right)\bigcap \mathit{\Gamma} \left(y\right)\right| $

(1)

其中：x和y分别代表网络中2个不同的节点；$ \mathit{\Gamma} （） $表示节点的所有邻居节点集合。

CN等价于2个节点间长度为2的路径数目：

$ {S}^{\mathrm{C}\mathrm{N}}={A}^{2} $

(2)

2）Salton又称余弦相似性指标，计算公式如下：

$ {s}_{xy}^{\mathrm{S}\mathrm{a}\mathrm{l}\mathrm{t}\mathrm{o}\mathrm{n}}=\frac{\left|\mathit{\Gamma} \left(x\right)\bigcap \mathit{\Gamma} \left(y\right)\right|}{\sqrt{{k}_{x}{k}_{y}}} $

(3)

其中：k代表节点的度。

3）Jaccard表示从节点对的任意一个节点的所有邻居中选择共同邻居节点的概率，计算公式如下：

$ {s}_{xy}^{\mathrm{J}\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}}=\frac{\left|\mathit{\Gamma} \left(x\right)\bigcap \mathit{\Gamma} \left(y\right)\right|}{\left|\mathit{\Gamma} \left(x\right)\bigcup \mathit{\Gamma} \left(y\right)\right|} $

(4)

4）AA对CN指标进行改进，旨在通过为连接较少的邻居分配更多权重来提高共同邻居的准确性，其计算公式如下：

$ {s}_{xy}^{\mathrm{A}\mathrm{A}}=\sum\limits_{z\in \mathit{\Gamma} \left(x\right)\bigcap \mathit{\Gamma} \left(y\right)}\frac{1}{\mathrm{l}\mathrm{o}{\mathrm{g}}_a{k}_{z}} $

(5)

5）RA由复杂网络的资源配置过程所驱动，考虑节点对的所有共同邻居节点有且仅有一个单位资源，并将它平均分配给所有邻居节点，从而进行资源传递，其计算公式如下：

$ {s}_{xy}^{\mathrm{R}\mathrm{A}}=\sum\limits_{z\in \mathit{\Gamma} \left(x\right)\bigcap \mathit{\Gamma} \left(y\right)}\frac{1}{\left|\mathit{\Gamma} \left(z\right)\right|} $

(6)

6）LP又称局部路径指标，在CN的基础上引入三阶路径指标，并给予三阶路径一个惩罚因子，其计算公式如下：

$ {S}^{\mathrm{L}\mathrm{P}}={A}^{2}+\alpha {A}^{3} $

(7)

7）Katz指标考虑节点对之间所有路径的集合，路径的长度以指数方式衰减，从而给较短路径更多的权重。由于该指标是基于整个网络的拓扑结构，因此其计算成本通常比局部指标高，而精确度往往也高于局部指标。Katz指标的计算公式如下：

$ {S}^{\mathrm{K}\mathrm{a}\mathrm{t}\mathrm{z}}={(I-\alpha \cdot A)}^{-1}-I $

(8)

1.2 本文评价指标

本文使用2个公认的链路预测常用指标对预测精度进行描述：

1）AUC，表示ROC曲线下的面积^[25]，是应用最广泛的链路预测性能评价指标之一。AUC表示随机选择的一个缺失连边的相似性得分高于随机选择的一个不存在连边的相似性得分的概率^[26]。如果采用随机选择的方式，在多次独立重复实验后，AUC的值应当是0.5。链路预测方法需要提高这个概率，即AUC的值越大，说明该方法越精确。假设进行n次取样，则AUC的计算公式如式（9）所示：

$ {A}_{\mathrm{A}\mathrm{U}\mathrm{C}}=\frac{n\text{'}+0.5n\text{'}\text{'}}{n} $

(9)

其中：n'代表测试集中边分数值大于不存在边的分数值的次数；n″表示两者分数值相等的次数。

2）Precision，表示前L条边中有m条边预测准确的比例，即排在前L条的边中有m条属于测试集。与AUC不同，Precision只关心前L条边是否预测准确^[27]，Precision在某些特定情形下（如只关注排在前L条边的预测准确与否）比AUC更有意义。Precision计算公式如下：

$ {P}_{\mathrm{P}\mathrm{r}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}}=\frac{m}{L} $

(10)

2 网络资源流量方法 2.1 网络资源流量评估方法

受到网络资源分配的启发，本文将节点对之间路径上的中间节点作为资源传输的媒介，通过计算节点对之间网络资源流量的总和，提出一种RF（Resource Flow）方法以计算节点对的相似性。首先，网络中的每个节点都有一定单位的初始资源，且这个资源可以根据节点的度大小进行传输，进而将2个节点之间的相似度计算转变为2个节点之间所有阶路径资源流量的计算，如果2个节点之间资源流量越多，说明它们的联系越紧密，则相似性越高。

如图 1所示，假设该无向图中存在15个节点和15条边，节点1和节点5没有直接相连，而是通过一条2阶路径和一条3阶路径相连，这2条路径经过的中间节点被标记为黑色。路径资源流量方法的思想是：给予网络中被预测的节点对（节点1和节点5）一定单位的初始资源R，该资源会按照均分的原则传输到节点对的所有邻居节点中，邻居节点在接收资源后会继续平均传给其所有的邻居节点。此时，初始资源R就会在网络中进行流动，可以通过计算节点1流向节点5的初始资源流量和节点5流向节点1的初始资源流量之和，得到节点对（节点1和节点5）的相似性分数。资源流量越多，说明这2个节点越相似。

2.2 网络资源流量量化

本文对网络资源流量量化作出如下定义：

定义1   假设存在无向网络G（V，E），网络中共有n个节点，i表示节点序号。在初始情况下，赋予每个节点$ {v}_{i}\in V $的资源表示为：

$ \sum\limits_{i=1}^{n}{R}_{i}=({R}_{1}, {R}_{2}, \cdots , {R}_{n}) $

(11)

定义2   网络分为动态和静态2种状态，在动态时，网络中的节点会向自己的邻居节点传输资源，而在静态时不会传输。2种状态的集合表示为：

$ G\in \left\{{G}_{\mathrm{S}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{c}}, {G}_{\mathrm{D}\mathrm{y}\mathrm{n}\mathrm{a}\mathrm{m}\mathrm{i}\mathrm{c}}\right\} $

(12)

定义3   在动态网络中，节点会向每个邻居节点传输资源，传输的资源量统一按照均分的原则分配给每一个邻居节点，即节点向每个邻居节点传输等量的资源。同时，节点也会接收来自邻居节点传输的资源，接收量取决于邻居节点的传输量。节点向其邻居发送的资源和从邻居处接收的资源分别如下：

$ \begin{array}{l}\sum\limits_{i=1}^{n}{R}_{i\to z\in \mathit{\Gamma} \left(i\right)}=\frac{{R}_{i}}{{k}_{i}}\\ \sum\limits_{i=1}^{n}{R}_{i\leftarrow z\in \mathit{\Gamma} \left(i\right)}=\frac{{R}_{z\in \mathit{\Gamma} \left(i\right)}}{{k}_{i}}\end{array} $

(13)

其中：$ k $是节点的度；$ z\in \mathit{\Gamma} \left(i\right) $表示节点$ {v}_{i} $的邻居节点；$ {R}_{i\to z\in \mathit{\Gamma} \left(i\right)} $表示$ {v}_{i} $向其邻居发送的资源；$ {R}_{i\leftarrow z\in \mathit{\Gamma} \left(i\right)} $表示节点$ {v}_{i} $从其邻居处接收的资源。

定义4   为了表示路径中节点对于资源量的传输作用，提出一个新的概念，即路径节点n。给定一对节点（x，y），$ l $为它们之间路径的最大长度。假设在节点x到节点y之间的长度为1~$ l $的路径上存在一些中间节点，将这些节点定义为中间路径节点。x和y之间的中间路径节点可以用集合表示为：

$ {n}_{x, y}=\{{n}_{x, y}^{1}, {n}_{x, y}^{2}, \cdots , {n}_{x, y}^{m}\} $

(14)

在节点$ {v}_{i} $到节点$ {v}_{j} $的某条路径中，依次经过m个节点，第1个节点为1阶路径节点，第2个节点为2阶路径节点，第m个节点为m阶路径节点。m取值为0~（l$ - $1）范围内的正整数，当m=0时，代表2个节点之间没有任何一条路径将它们相连。路径节点的数目为路径数目减1，即l$ - $1。由$ {v}_{i} $到$ {v}_{j} $和由$ {v}_{j} $到$ {v}_{i} $，路径节点索引值相加为m+1，即：

$ {n}_{ij}^{1}={n}_{ji}^{m} \\ {n}_{ji}^{1}={n}_{ij}^{m} $

(15)

定义5   在一个动态网络中，给定一对节点$ (x, y) $，节点之间的路径长度为l，它们之间流动的资源总量可以通过2个步骤进行计算：首先，节点x和节点y分别将初始资源发送给邻居；然后，在x和y之间路径上的资源流将由中间路径节点分别发送到其邻居节点。每个中间路径节点将从邻居处接收资源，并将资源平均交付给下一个中间路径节点，因此，在交付之前资源量是$ 1/(k-1) $。根据RF指标的定义，随着路径数的增加，资源流量经过的路径节点增多，初始资源会被不断稀释，称其为路径稀释作用。资源流量计算过程如图 2所示。

假设节点x和节点y向相邻节点传输R个单位的资源，节点间路经上的总资源流量计算分为两步：

1）第一步，计算节点x和节点y发送给邻居的初始资源，即：

$ {R}_{x, y}=\left(\frac{{R}_{x}}{{k}_{x}}+\frac{{R}_{y}}{{k}_{y}}\right) $

(16)

2）第二步，计算路径长度为l$ - $1的中间路径节点的贡献值，即：

$ {\omega }_{xy}^{l-1}=\prod\limits_{m=1}^{l-1}\frac{1}{{k}_{{n}_{x, y}^{m}}-1} $

(17)

其中：$ {n}_{x, y}^{m} $表示从x到y的m阶中间路径节点；$ {\omega }_{xy}^{l-1} $表示在长度为l$ - $1的中间路径节点稀释贡献值的累加。在计算$ {\omega }_{xy}^{} $时，需要考虑资源的双向流动，即从x到y和从y到x。$ {\omega }_{xy}^{} $的值越高，则一对节点$ (x, y) $之间的贡献值越大。

定义6   给定一对节点$ (x, y) $，$ l $是它们之间路径的最大长度。$ {h}_{x, y}^{m} $表示从节点x到节点y的长度为m+1的所有路径个数。$ x\mathrm{、}y $之间所有中间路径节点的贡献即为x和y之间双向流动的资源之和，表示如下：

$ {S}_{x, y}=\sum\limits_{i=1}^{{h}_{x, y}^{1}}{R}_{x, y}{\omega }_{xy}^{1}+\sum\limits_{i=1}^{{h}_{x, y}^{2}}{R}_{x, y}{\omega }_{xy}^{2}+\cdots +\sum\limits_{i=1}^{{h}_{x, y}^{l-1}}{R}_{x, y}{\omega }_{xy}^{l-1} $

(18)

不同节点在网络中的重要性不同，为了突显这个特征，需要给每个节点分配不同的初始资源。一般地，节点的重要性用“中心性”来衡量。本文利用2阶局部指标（即该节点与其他节点存在共同邻居节点的比例）来进行初始资源分配。如果网络中的一个节点与其他n$ - $1个节点之间存在的共同邻居数目越多，则认为该节点越重要，给它分配更多的资源，用节点邻居数与其余节点总数的比值来表示，即：

$ \begin{array}{l}{R}_{i}=\frac{\sum\limits_{j=1}^{n-1}{a}_{j}}{n-1}\text{，}i, j\in n\text{，}i\bigcup j=n\text{，}i\bigcap j=\mathrm{\varnothing }\\ {a}_{j}=\left\{\begin{array}{l}1, i\mathrm{与}j\mathrm{之}\mathrm{间}\mathrm{存}\mathrm{在}\mathrm{共}\mathrm{同}\mathrm{邻}\mathrm{居}\\ 0, i\mathrm{与}j\mathrm{之}\mathrm{间}\mathrm{不}\mathrm{存}\mathrm{在}\mathrm{共}\mathrm{同}\mathrm{邻}\mathrm{居}\end{array}\right.\end{array} $

(19)

其中：R_i代表第i个节点的初始资源。

2.3 链路预测求解

本文算法的输入变量是无向网络，需要计算节点对（x，y）的相似性和中间路径节点的阶数$ l $。输入无向网络G之后，首先将其转换为邻接矩阵的形式，以得到所有节点和连边的信息，然后计算所有节点的初始资源和它们的度，得到2个n维向量，数值对应于每一个节点的资源和度。对于给定的节点对（x，y），使用深度优先遍历方法找出网络中的所有路径，假设网络有n个节点，花费的时间复杂度为O（n²）。这些路径中的节点除了起点和终点之外都是中间节点。假设考虑1阶到l$ - $1阶的所有中间节点的作用，并且遍历出的所有路径数为k，那么该过程的时间复杂度就为O（k（l$ - $1）），因此，RF算法总的时间复杂度为O（n²+k（l$ - $1）），$ l $的最大值为n$ - $2，即x经过除x、y节点之外的所有节点到达y，时间复杂度最高为O（n²+kn$ - $3k）。RF算法描述如下：

算法1   RF算法

输入  无向图$ G(V, E) $，节点对$ (x, y) $，中间路径节点阶数l

输出  相似性指标$ {S}_{x, y} $

1.For all the node $ {\mathrm{v}}_{\mathrm{i}} $ in $ \mathrm{V} $

2.Calculate the initial resource $ {\mathrm{R}}_{\mathrm{i}} $

3.Calculate the degree $ {\mathrm{k}}_{\mathrm{i}} $

4.End

5.Calculate delivery initial resource in step 1：

$ {\mathrm{R}}_{\mathrm{x}, \mathrm{y}}=\frac{{\mathrm{R}}_{\mathrm{x}}}{{\mathrm{k}}_{\mathrm{x}}}+\frac{{\mathrm{R}}_{\mathrm{y}}}{{\mathrm{k}}_{\mathrm{y}}} $

6.Search all the path between x and y，n is the number of all the paths

7.For path in range 1 to n

8.Calculate the intermediate path nodes contribution $ \sum\limits_{1}^{\mathrm{n}}\prod\limits_{\mathrm{i}}^{\mathrm{l}-1}{\mathrm{\omega }}_{\mathrm{x}\mathrm{y}}^{\mathrm{i}} $

9.End

10.Calculate $ {\mathrm{S}}_{\mathrm{x}, \mathrm{y}}=\sum\limits_{1}^{\mathrm{n}}\left({\mathrm{R}}_{\mathrm{x}, \mathrm{y}}\times {\prod\limits_{\mathrm{i}}^{\mathrm{l}-1}\mathrm{\omega }}_{\mathrm{x}\mathrm{y}}^{\mathrm{i}}\right) $

11.Return $ {\mathrm{S}}_{\mathrm{x}, \mathrm{y}} $

3 实验结果与分析

为了评估本文所提链路预测算法RF的性能，将其与目前最常用的7种链路预测基准方法进行实验对比与分析。

3.1 数据集

实验使用来自真实世界的11个不同的复杂网络数据集，这些数据集来源于多种不同的网络，如社交网络、生物网络、交通信息网络以及引文网络等。11个网络数据集的具体信息如下：

1）NS^[28]：科学引文合作网络，代表论文之间的引用合作关系。

2）PB^[29]：美国政客之间的博客交互网络。

3）Yeast^[30]：大型蛋白质相互作用网络，包含2 375个节点和11 693个链接。

4）Jazz^[31]：爵士乐音乐家之间的合作网络，代表音乐作品之间的合作关系。

5）Metabolic^[32]：秀丽隐杆线虫新陈代谢网络。

6）BUP^[33]：某政客博客网络。

7）UAL^[34]：飞机交通系统网络。

8）INF^[35]：展览中观众面对面接触的网络。

9）SMG^[36]：不同研究领域作者的论文合作网络。

10）Celegans^[37]：秀丽隐杆线虫的神经网络。

11）EML^[38]：罗维拉大学成员之间的电子邮件交互网络。

11个网络的基本拓扑信息具体如表 1所示。

3.2 不同参数情况下的RF预测精确度

考虑到RF的时间复杂度过高会大幅提高对比实验的难度，此外，针对路径信息的方法，利用2阶路径和3阶路径的信息最为准确，从4阶之后准确度开始下降^[39]。因此，本文只考虑1阶、2阶、3阶的中间路径节点，通过设置$ l $值为4来降低时间复杂度，最终时间复杂度为O（n²+3k），从而在计算复杂度不高的同时最大化地提升准确度。首先，只利用RF算法计算11个网络中的AUC和Precision，横向对比RF在利用不同阶数的路径节点时的性能表现。本节与下一节的实验中统一设置训练集与测试集的比例为9∶1。

1阶、2阶、3阶路径节点的所有组合共有7种（$ {C}_{3}^{3}+{C}_{3}^{2}+{C}_{3}^{1} $），分别是RF-1、RF-2、RF-3、RF-1+2、RF-1+3、RF-2+3、RF-1+2+3，数字的含义表示RF在链路预测过程中利用到的路径节点的阶数，如RF-1表示只利用1阶路径节点，RF-2+3表示利用2阶和3阶路径节点。AUC和Precision运行结果分别如表 2和表 3所示，其中，最优结果加粗表示。

从图 3、图 4可以得出如下结论：

1）对比RF利用单阶路径节点时的精准度情况。RF-1在4个数据集中AUC表现最佳，在3个数据集中Precision表现最佳；RF-2在5个数据集中AUC表现最佳，AUC表现情况良好，在7个数据集中Precision表现最佳；RF-3在2个数据集中AUC表现最佳，AUC表现情况较差，Precision只在1个数据集中超过了RF-1、RF-2。因此，如果RF算法只利用3阶路径节点，则其AUC和Precision的精准度将远低于RF-1、RF-2。RF-2的表现良好，超过了RF-1，这意味着资源在3阶路径中的传输精度高于2阶路径，这打破了以往指标对于共同邻居的精度普遍高于3阶路径这一共识，这一点在文献[17, 40-41]中进行了证实，本文也进一步验证了这个情况。

2）对比RF利用多阶路径节点时的精准度情况。RF-1+2在6个数据集中AUC表现最佳，但Precision只在3个数据集中表现最佳；RF-2+3在5个数据集中AUC表现最佳，在7个数据集中Precision表现最佳；RF-1+3的AUC表现最差，未在任何数据集中超过RF-1+2和RF-2+3，其Precision也只在1个数据集中超过了RF-1+2、RF-2+3；RF-1+2+3在11个数据集中AUC和Precision的表现超过了其他所有的6种情况，RF-1+2+3仅利用了4个阶数的路径节点，其利用网络拓扑信息的程度最高，虽然计算复杂度会提升，但能保证结果较优。

基于以上分析，本文得到RF的最优指标设置为RF-opt=RF-1+2+3，在后续实验中，会以RF-opt的数据与其他基准指标进行对比。

3.3 预测精度对比分析

为了验证RF指标的预测精度，本文将其与上文提到的7个基准指标在11个网络中进行对比，包括5个局部指标（CN、Salton、Jaccard、AA、RA）、1个准局部指标（LP）以及1个全局指标（Katz）。表 4展示各指标在11个网络中的AUC值对比情况，最优结果加粗表示。从表 4可以看出，RF指标在7个数据集中表现最优，虽然RF只利用了准局部信息，但是其表现并不逊于全局指标Katz，Katz只在2个数据集中表现最优。在基于局部信息的相似性指标中，CN、Salton、Jaccard和AA指标在不同网络中表现相近，不如准局部和全局指标。RA指标由于利用了网络资源的机制，相比于其他4种局部指标表现更优，在Metabolic数据集中达到了最优效果。RF指标除了在个别数据集中表现不如RA、LP和Katz，在其他数据集中表现均为最优，相比于全局指标，RF作为准局部指标，其在预测精度上更有优势。

表 5所示为各指标在11个网络中的Precision值对比。从表 5可以看出，RF指标在8个数据集中表现最优，在Yeast和SMG数据集中其表现远超其他指标。准局部指标LP和全局指标Katz表现良好，普遍优于局部指标，分别在EML和UAL数据集中达到最优，这在AUC和Precision中都表现出了同样的结果，说明准局部指标和全局指标挖掘了更多的网络信息，因此，它们的精准度高于局部指标。

综上所述，相比于其他7种基准指标，RF指标能够达到更优的预测精准度，原因主要有以下3点：

1）相比于局部指标CN、Salton、Jaccard、AA和RA，RF指标对于共同邻居节点的利用程度更高。

2）相比于准局部指标LP，RF利用了更多的网络信息，考虑到了路径节点本身的度大小对于链路预测贡献不同的情况。

3）全局指标Katz很少利用高阶路径信息，并且予以非常大的惩罚因数，导致添加了很多数值较小的噪声，提高了计算复杂度。RF只从1阶、2阶、3阶路径节点出发，避免了噪声信息，同时降低了计算复杂度，因此，其精确度表现更优。

3.4 RF算法鲁棒性测试

为了更准确地验证RF的性能，将训练集划分比例从0.5调整到0.9，步长设为0.1，对8个算法在11个网络中的表现进行可视化，从而测试所有指标的鲁棒性，实验结果如图 5、图 6所示。从图 5可以看出，当训练集比例从0.5上升到0.9时，AUC值呈现上升趋势，当训练集比例增加时，随着网络已知信息的增加，所有方法的AUC值随之上升。在训练集比例的变化过程中，局部指标的斜率变化往往大于准局部和全局指标，鲁棒性最差。在所有指标中，Katz在NS、PB、Yeast数据集中AUC基本没有波动，鲁棒性较好。RF指标仅次于Katz指标，在多个数据集中波动不大，并且都优于其他指标。从图 6可以看出，所有方法的Precision值总体呈现下降趋势，说明随着训练集比例的升高，测试集比例减小，所有节点预测准确的概率降低。与AUC结果不同，RF的Precision鲁棒性在所有指标中表现最好，在总体波动不大的情况下还能保持较高的数值。在EML数据集中，RF的Precision波动较大，不过波动情况仍然低于其他指标，而在INF中，LP和Katz出现较大的波动，RF能够保持稳定，此外，RF在Celegans中不仅波动最小，而且始终优于其他指标。

4 结束语

链路预测方法受到拓扑结构复杂特征和系统动力学要素的制约，使得局部方法效率较低，全局方法则面临维数灾难问题。网络资源分配机制虽然能够在一定程度上实现资源的合理分配，但是忽略了传输路径节点的有效性和传输方向问题。此外，在当今的复杂网络研究中，数据集规模越来越大，对链路预测方法的效率和精度提出了更高的要求。为了解决上述问题，本文从准局部指标和资源流动角度出发，提出一种基于网络流量的链路预测方法。定义网络中初始资源的生成和资源流动机制，计算双向资源流量以精确刻画节点对之间的相似性，在此基础上提出相似性指标和链路预测算法RF。实验结果表明，将双向资源流量作为相似性的匹配度，可以使得预测精度显著提升，从而证实了资源传输机制的有效性。虽然本文的网络流量研究在上述方面具有一定的改进意义，但仍然存在局限性。由于算法复杂度的限制，网络更高阶的拓扑信息无法得到利用，且在初始资源分配的过程中，本文算法仍然采用较为朴素的公共近邻思想进行分配。下一步将优化算法流程以利用更高阶节点信息进行链路预测，同时，利用神经网络或网络嵌入技术对初始资源分配权重，以及将本文算法应用于加权网络、有向网络和大型网络中，也是今后的研究方向。