A Survey of Link Prediction in Complex Networks

1. INTRODUCTION

2. THE LINK PREDICTION PROBLEM

无向图的链路预测问题：给定时间t中无向网的 s n a p s h o t snapshot snapshot，其中每个节点代表一个实体或参与者，每个链接代表通过链接连接的成对实体之间的相互作用或关系。推断在当前 s n a p s h o t snapshot snapshot中丢失链接（存在但为观察到）或将在t+ δ \delta δ形成的链接。

2.1 Applications of Link Prediction

2.2 Terminology and Notation

G = ( V , E ) G = (V,E) G=(V,E) : 图或网络
V V V : 节点集合
E E E ： 边集合
e x , y e_{x,y} ex,y​ ： 节点 x x x与节点 y y y的链接
∣ V ∣ |V| ∣V∣ : 节点数目，网络的大小
∣ E ∣ |E| ∣E∣ ： 链接数目
Γ x \Gamma _x Γx​ : 节点 x x x的邻域节点集
∣ Γ x ∣ |\Gamma_x| ∣Γx​∣ : 节点 x x x的度

3. SIMILARITY-BASED METHODS

基于相似度的方法假定节点倾向于与其他相似节点形成链接，根据给定的距离函数，如果两个节点连接到相似节点或在网络中附近，则它们是相似的。、成对的节点根据其相似性评分以降序排列，因此，在排在最前面的链接更有可能出现在缺失链接集中。

相似性的定义不是一件容易的事，因为它具有启发式(heuristic)的成分。相似性可以根据网络拓扑属性来定义。

3.1 Local Approaches

基于局部相似性的方法使用与节点邻域相关的结构信息来计算每个节点与网络中其他节点的相似性。缺点为：在非小网络中，许多链接的形成，其距离都大于2。

3.1.1 Common neighbors (CN)

相似性函数为: s ( x , y ) = ∣ Γ x ⋂ Γ y ∣ s(x,y) = |\Gamma_x \bigcap\Gamma_y| s(x,y)=∣Γx​⋂Γy​∣

3.1.2 The Adamic-Adar index (AA)

基于两个实体的共享特征来度量两个实体之间的相似性，每个特征权重均会因其出现频率而受到对数惩罚。

相似性函数为： s ( x , y ) = ∑ z ∈ Γ x ⋂ Γ y 1 l o g ∣ Γ z ∣ s(x,y)=\sum_{z \in \Gamma_x \bigcap \Gamma_y} \frac {1} {log|\Gamma_z|} s(x,y)=z∈Γx​⋂Γy​∑​log∣Γz​∣1​

3.1.3 The resource allocation index (RA)

每个邻居节点从 x x x获取一个资源单元，并将其平均分配给其邻居。可以将节点 y y y获得的资源量视为两个节点之间的相似度。

相似性函数为: s ( x , y ) = ∑ z ∈ Γ x ⋂ Γ y 1 ∣ Γ z ∣ s(x,y)=\sum_{z \in \Gamma_x \bigcap \Gamma_y} \frac {1} {|\Gamma_z|} s(x,y)=z∈Γx​⋂Γy​∑​∣Γz​∣1​

3.1.4 Resource allocation based on common neighbor interactions (RA-CNI)

基于资源分配（即上述方法）此方法还考虑了相反方向的资源返回。

相似性函数为: s ( x , y ) = ∑ z ∈ Γ x ⋂ Γ y 1 ∣ Γ z ∣ + ∑ e i , j ∈ E , ∣ Γ i ∣ < ∣ Γ j ∣ , i ∈ Γ x , j ∈ Γ y ( 1 ∣ Γ i ∣ + 1 ∣ Γ j ∣ ) s(x,y)=\sum_{z \in \Gamma_x \bigcap \Gamma_y} \frac {1} {|\Gamma_z|} + \sum_{e_{i,j}\in E,|\Gamma_i|<|\Gamma_j|,i \in \Gamma_x, j \in \Gamma_y} (\frac {1} {|\Gamma_i|} + \frac {1} {|\Gamma_j|}) s(x,y)=z∈Γx​⋂Γy​∑​∣Γz​∣1​+ei,j​∈E,∣Γi​∣<∣Γj​∣,i∈Γx​,j∈Γy​∑​(∣Γi​∣1​+∣Γj​∣1​)

3.1.5 The preferential attachment index (PA)

相似性函数为: s ( x , y ) = ∣ Γ x ∣ ∣ Γ y ∣ s(x,y)=|\Gamma_x||\Gamma_y| s(x,y)=∣Γx​∣∣Γy​∣
PS: 预测准确性通常很差

3.1.6 The Jaccard index (JA)

相似性函数为: s ( x , y ) = ∣ Γ x ⋂ Γ y ∣ ∣ Γ x ⋃ Γ y ∣ s(x,y) = \frac {|\Gamma_x \bigcap \Gamma_y|} {|\Gamma_x \bigcup \Gamma_y|} s(x,y)=∣Γx​⋃Γy​∣∣Γx​⋂Γy​∣​

3.1.7 The Salton index (SA)

The Salton index 又称余弦相似度

相似性函数为: s ( x , y ) = ∣ Γ x ⋂ Γ y ∣ ∣ Γ x ∣ ∣ Γ y ∣ s(x,y) = \frac{|\Gamma_x \bigcap \Gamma_y|} {\sqrt{|\Gamma_x||\Gamma_y|}} s(x,y)=∣Γx​∣∣Γy​∣ ​∣Γx​⋂Γy​∣​

3.1.8 The Sørensen index (SO)

这个指数由植物学家同于比较不同生态群落样本之间的相似性，对异常值的敏感度较低。

相似性函数为: s ( x , y ) = 2 ∣ Γ x ⋂ Γ y ∣ ∣ Γ x ∣ + ∣ Γ y ∣ s(x,y) = \frac {2 |\Gamma_x \bigcap \Gamma_y|} {|\Gamma_x|+|\Gamma_y|} s(x,y)=∣Γx​∣+∣Γy​∣2∣Γx​⋂Γy​∣​

3.1.9 The hub promoted index (HPI)

该指数是研究代谢网络中模块性的结果,这些网络显示了一个层次结构，其中包含小型的高度内部连接的模块，这些模块也彼此高度隔离。这种相似性度量的主要目标是避免在集线器节点之间形成链接，并促进低度节点与集线器之间的链接形成。

相似性函数为: s ( x , y ) = ∣ Γ x ⋂ Γ y ∣ m i n ( Γ x , Γ y ) s(x,y) = \frac {|\Gamma_x \bigcap \Gamma_y|} {min(\Gamma_x,\Gamma_y)} s(x,y)=min(Γx​,Γy​)∣Γx​⋂Γy​∣​

3.1.10 The hub depressed index (HDI)

与上个相似性度量目标相反，促进集线器之间以及低度节点之间的链接形成，但不能促进集线器和低度节点之间的链接形成。

相似性函数为: s ( x , y ) = ∣ Γ x ⋂ Γ y ∣ m a x ( Γ x , Γ y ) s(x,y) = \frac {|\Gamma_x \bigcap \Gamma_y|} {max(\Gamma_x,\Gamma_y)} s(x,y)=max(Γx​,Γy​)∣Γx​⋂Γy​∣​

3.1.11 The local Leicht-Holme-Newman index (LLHN)

此方法的作者宣称，该指数比Salton指数或Jaccard指数对结构等效性更为敏感。

相似性函数为: s ( x , y ) = Γ x ⋂ Γ y ∣ Γ x ∣ ∣ Γ y ∣ s(x,y) = \frac {\Gamma_x \bigcap \Gamma_y} {|\Gamma_x||\Gamma_y|} s(x,y)=∣Γx​∣∣Γy​∣Γx​⋂Γy​​

3.1.12 The individual attraction index (IA)

两个节点的邻域也高度连接的情况下，更有可能建立连接。

相似性函数1为： s ( x , y ) = ∑ z ∈ Γ x ⋂ Γ y ∣ e z , Γ x ⋂ Γ y ∣ + 2 ∣ Γ z ∣ s(x,y) = \sum_{z \in \Gamma_x \bigcap \Gamma_y} \frac {|e_{z,\Gamma_x \bigcap \Gamma_y}|+2} {|\Gamma_z|} s(x,y)=z∈Γx​⋂Γy​∑​∣Γz​∣∣ez,Γx​⋂Γy​​∣+2​

• ∣ e z , Γ x ⋂ Γ y ∣ |e_{z,\Gamma_x \bigcap \Gamma_y}| ∣ez,Γx​⋂Γy​​∣ : the number of links between node z z z and nodes from the set Γ x ⋂ Γ y \Gamma_x \bigcap \Gamma_y Γx​⋂Γy​

相似性函数2为: s ( x , y ) = ∑ z ∈ Γ x ⋂ Γ y ∣ e Γ x ⋂ Γ y ∣ + 2 ∣ Γ z ∣ ∣ Γ x ⋂ Γ y ∣ s(x,y) = \sum_{z \in \Gamma_x \bigcap \Gamma_y} \frac {|e_{\Gamma_x \bigcap \Gamma_y}|+2} {|\Gamma_z||\Gamma_x \bigcap \Gamma_y|} s(x,y)=z∈Γx​⋂Γy​∑​∣Γz​∣∣Γx​⋂Γy​∣∣eΓx​⋂Γy​​∣+2​

• ∣ e Γ x ⋂ Γ y ∣ |e_{\Gamma_x \bigcap \Gamma_y}| ∣eΓx​⋂Γy​​∣ : the number of edges in the network that connect common neighbors of nodes x x x and y y y

相似性函数2的复杂性比函数1要低

3.1.13 Mutual information (MI)

从信息论的角度出发，在给定公共邻居集合的情况下，计算链接存在的条件性自信息。

相似性函数为： s ( x , y ) = − I ( e x , y ∣ Γ x ⋂ Γ y ) = − I ( e x , y ) + ∑ z ∈ Γ x ⋂ Γ y I ( e x , y ; z ) s(x,y) = -I(e_{x,y}|\Gamma_x \bigcap \Gamma_y)=-I(e_{x,y})+\sum_{z \in \Gamma_x \bigcap \Gamma_y}I(e_{x,y};z) s(x,y)=−I(ex,y​∣Γx​⋂Γy​)=−I(ex,y​)+z∈Γx​⋂Γy​∑​I(ex,y​;z)

• I ( e x , y ) I(e_{x,y}) I(ex,y​) ： 节点 x , y x,y x,y链接的自信息
• I ( e x , y ; z ) I(e_{x,y};z) I(ex,y​;z) ： 节点 x , y x,y x,y之间的链接与公共邻居节点的互信息 I ( e x , y ; z ) = 1 ∣ Γ z ∣ ∣ Γ z − 1 ∣ ∑ u , v ∈ Γ z : u ≠ v ( I ( e u , v − I ( e u , v ∣ ∣ z ) ) I(e_{x,y};z)=\frac {1} {|\Gamma_z||\Gamma_z-1|} \sum_{u,v \in \Gamma_z:u \not= v}(I(e_{u,v}-I(e_{u,v|}|z)) I(ex,y​;z)=∣Γz​∣∣Γz​−1∣1​u,v∈Γz​:u​=v∑​(I(eu,v​−I(eu,v∣​∣z))
• I ( e x , y ∣ z ) I(e_{x,y}|z) I(ex,y​∣z) ： 节点 x , y x,y x,y链接的条件自信息
  I ( e x , y ∣ z ) = − l o g 2 ∣ { e x , y : x , y ∈ Γ z , e x , y ∈ E } ∣ 1 2 ∣ Γ z ∣ ∣ Γ z − 1 ∣ I(e_{x,y}|z)=-log_2 \frac {|\{e_{x,y}:x,y \in \Gamma_z,e_{x,y} \in E\}|} {\frac {1} {2} |\Gamma_z||\Gamma_z-1|} I(ex,y​∣z)=−log2​21​∣Γz​∣∣Γz​−1∣∣{ex,y​:x,y∈Γz​,ex,y​∈E}∣​

3.1.14 Local Naive Bayes (LNB)

此方法假设每个共享的邻居有不同的作用或影响程度。

相似性函数为: s ( x , y ) = ∑ z ∈ Γ z ⋂ Γ y f ( z ) l o g ( o R z ) s(x,y) = \sum_{z \in \Gamma_z \bigcap \Gamma_y} f(z)log(oR_z) s(x,y)=z∈Γz​⋂Γy​∑​f(z)log(oRz​)

• o o o ：常数
  o = P u n c o n n e c t e d P c o n n e c t e d = 1 2 ∣ V ∣ ( ∣ V ∣ − 1 ) ∣ E ∣ − 1 o=\frac {P_{unconnected}} {P_{connected}}=\frac {\frac {1} {2}|V|(|V|-1)} {|E|}-1 o=Pconnected​Punconnected​​=∣E∣21​∣V∣(∣V∣−1)​−1
• R z R_z Rz​：节点的作用或影响程度
  R z = 2 ∣ { e x , y : x , y ∈ Γ z , e x , y ∈ E } ∣ + 1 2 ∣ { e x , y : x , y ∈ Γ z , e x , y ∉ E } ∣ + 1 R_z=\frac {2|\{e_{x,y}:x,y \in \Gamma_z,e_{x,y} \in E\}|+1} {2|\{e_{x,y}:x,y \in \Gamma_z,e_{x,y} \notin E\}|+1} Rz​=2∣{ex,y​:x,y∈Γz​,ex,y​∈/​E}∣+12∣{ex,y​:x,y∈Γz​,ex,y​∈E}∣+1​
• f ( z ) f(z) f(z)：衡量节点影响的函数
  • 对于common neighbors， f ( z ) = 1 f(z)=1 f(z)=1
  • 对于Adamic-Adar index, f ( z ) = 1 l o g ∣ Γ z ∣ f(z)=\frac {1} {log|\Gamma_z|} f(z)=log∣Γz​∣1​
  • 对于resource allocation method, f ( z ) = 1 ∣ Γ z ∣ f(z)=\frac {1} {|\Gamma_z|} f(z)=∣Γz​∣1​

3.1.15 CAR-based indices (CAR)

如果两个节点的共同邻居是一个内部紧密联系的队列成员，则这两个节点更可能被链接。这种假设使我们可以更加重视与其他邻居互连的节点。

相似性函数为: s ( x , y ) = ∑ z ∈ Γ ) x ⋂ Γ y 1 + ∣ Γ x ⋂ Γ y ⋂ Γ z ∣ 2 s(x,y) = \sum_{z \in \Gamma)x \bigcap \Gamma_y} 1 + \frac {|\Gamma_x \bigcap \Gamma_y \bigcap \Gamma_z|} {2} s(x,y)=z∈Γ)x⋂Γy​∑​1+2∣Γx​⋂Γy​⋂Γz​∣​

3.1.16 Functional similarity weight (FSW)

基于 S ø r e n s e n Sørensen Sørensen I n d e x Index Index (索伦森指数)

相似性函数为： s ( x , y ) = ( 2 ∣ Γ x ⋂ Γ y ∣ ∣ Γ x − Γ y ∣ + 2 ∣ Γ x ⋂ Γ y ∣ + λ ) 2 s(x,y) = (\frac {2|\Gamma_x \bigcap \Gamma_y|} {|\Gamma_x - \Gamma_y|+2|\Gamma_x \bigcap \Gamma_y|+\lambda})^2 s(x,y)=(∣Γx​−Γy​∣+2∣Γx​⋂Γy​∣+λ2∣Γx​⋂Γy​∣​)2

• λ \lambda λ : 当链接节点中的任何一个具有较小度时，包含此参数是为了惩罚节点之间的相似性。
  λ = m a x ( 0 , < Γ > − ( ∣ Γ x − Γ y ∣ + ∣ Γ x ⋂ Γ y ∣ ) ) \lambda=max(0,<\Gamma>-(|\Gamma_x - \Gamma_y|+|\Gamma_x \bigcap \Gamma_y|)) λ=max(0,<Γ>−(∣Γx​−Γy​∣+∣Γx​⋂Γy​∣))

3.1.17 Local interacting score (LIT)

此方法为相似权重的迭代变化。初始时，将已经连接的边初始为 s x , y ( 0 ) = 1 s^{x,y}(0)=1 sx,y(0)=1，其他置为 s x , y ( 0 ) = 0 s^{x,y}(0)=0 sx,y(0)=0,

相似性函数为: s x , y ( t ) = ∑ u ∈ Γ x ⋂ Γ y s z , x ( t − 1 ) + ∑ v ∈ Γ x ⋂ Γ y s z , y ( t − 1 ) ∑ u ∈ Γ x s z , x ( t − 1 ) + ∑ v ∈ Γ y s z , y ( t − 1 ) + λ ( x ) + λ ( y ) s^{x,y}(t)=\frac {\sum_{u \in \Gamma_x \bigcap \Gamma_y}s^{z,x}(t-1) + \sum_{v \in \Gamma_x \bigcap \Gamma_y}s^{z,y}(t-1)} {\sum_{u \in \Gamma_x}s^{z,x}(t-1)+\sum_{v \in \Gamma_y} s^{z,y}(t-1)+\lambda(x)+\lambda(y)} sx,y(t)=∑u∈Γx​​sz,x(t−1)+∑v∈Γy​​sz,y(t−1)+λ(x)+λ(y)∑u∈Γx​⋂Γy​​sz,x(t−1)+∑v∈Γx​⋂Γy​​sz,y(t−1)​

• λ ( x ) \lambda(x) λ(x) ： 在相似权重中扮演 λ \lambda λ惩罚的角色
  λ ( x ) = m a x ( 0 , ∑ u ∈ V ∑ v ∈ Γ u s u , x ( t ) / ∣ V ∣ − ∑ z ∈ Γ x ⋂ Γ y s z , x ( t − 1 ) \lambda(x) = max(0, \sum_{u \in V}\sum_{v \in \Gamma_u}s^{u,x}(t)/|V|-\sum_{z \in \Gamma_x \bigcap \Gamma_y}s^{z,x}(t-1) λ(x)=max(0,u∈V∑​v∈Γu​∑​su,x(t)/∣V∣−z∈Γx​⋂Γy​∑​sz,x(t−1)

PS： 上述相似性函数感觉有错误，应改为：
s x , y ( t ) = ∑ u ∈ Γ x ⋂ Γ y s u , x ( t − 1 ) + ∑ v ∈ Γ x ⋂ Γ y s v , y ( t − 1 ) ∑ u ∈ Γ x s u , x ( t − 1 ) + ∑ v ∈ Γ y s v , y ( t − 1 ) + λ ( x ) + λ ( y ) s^{x,y}(t)=\frac {\sum_{u \in \Gamma_x \bigcap \Gamma_y}s^{u,x}(t-1) + \sum_{v \in \Gamma_x \bigcap \Gamma_y}s^{v,y}(t-1)} {\sum_{u \in \Gamma_x}s^{u,x}(t-1)+\sum_{v \in \Gamma_y} s^{v,y}(t-1)+\lambda(x)+\lambda(y)} sx,y(t)=∑u∈Γx​​su,x(t−1)+∑v∈Γy​​sv,y(t−1)+λ(x)+λ(y)∑u∈Γx​⋂Γy​​su,x(t−1)+∑v∈Γx​⋂Γy​​sv,y(t−1)​

3.2 Global Approaches

基于全局相似度的索引使用整个网络的拓扑信息对每个链接进行评分。这些方法不限于测量距离两个节点之间的相似性。但是，它们的计算复杂性可能使它们对于大型网络不可行，并且其并行化可能非常复杂。

3.2.1 Negated shortest path (NSP)

此方法需要计算一对节点的最短路径，基于 D i j k s t r a Dijkstra Dijkstra算法。与大部分 L o c a l Local Local M e t h o d s Methods Methods方法相比，其预测精度也很差。

相似性函数为： s ( x , y ) = − ∣ s h o r t e s t p a t h x , y ∣ s(x,y) = -|shortest path_{x,y}| s(x,y)=−∣shortestpathx,y​∣

3.2.2 The Katz index (KI)

此方法计算了一对节点所有可能路径的影响，并用其长度来逐渐惩罚路径。

相似性函数为: s ( x , y ) = ∑ l = 1 ∞ β l ∣ p a t h s x , y l ∣ = ∑ l = 1 ∞ β l ( A l ) x , y s(x,y) = \sum_{l=1}^{\infty} \beta^l|paths^l_{x,y}| = \sum_{l=1}^{\infty}\beta^l(A^l)_{x,y} s(x,y)=l=1∑∞​βl∣pathsx,yl​∣=l=1∑∞​βl(Al)x,y​

• p a t h s x , y l paths^l_{x,y} pathsx,yl​：节点 x , y x,y x,y长度为 l l l的路径集合
• A A A：图网络的邻接矩阵，矩阵的 l l l次幂表示节点对长度为 l l l路径计数
• β \beta β： d a m p i n g damping damping f a c t o r factor factor（惩罚因子） 0 < β < 1 0<\beta<1 0<β<1，其值越大说明对长路径的重视程度越高

论文提出：相似度矩阵 S S S的表达式。（并没有给出具体证明）

现给出我的理解，并简单证明如下：
由于： S = ∑ l = 1 ∞ β l A l S=\sum_{l=1}^{\infty}\beta^lA^l S=∑l=1∞​βlAl
现对相似矩阵的对角元素+1，所以就有： T = S + I = β A ( I + S ) = β A T + I T=S+I=\beta A(I+S)=\beta A T + I T=S+I=βA(I+S)=βAT+I
解得 ： T = ( I − β A ) − 1 T=(I-\beta A)^{-1} T=(I−βA)−1

相似性矩阵为:
S = ( I − β A ) − 1 − I S=(I-\beta A)^{-1}-I S=(I−βA)−1−I

K a t z Katz Katz指数具有强大的预测能力，但计算矩阵逆的复杂度将其适用性限制在小型网络中。

3.2.3 The global Leicht-Holme-Newman index (GLHN)

与 K a t z Katz Katz指数原理相同，此方法设定与节点路径数成正比的相似度。

相似矩阵为：
S = I + ∑ l = 1 ∞ ϕ l A l S = I + \sum_{l=1}^{\infty}\phi^lA^l S=I+l=1∑∞​ϕlAl

• 单位矩阵表示其最大自相似度
• 参数 ϕ \phi ϕ与 K a t z Katz Katz指数的惩罚因子 β \beta β类似

每对节点之间长度为 l l l的路径数可用其期望值代替。
E x p e c t e d ( ( A l ) x , y ) = ∣ Γ x ∣ ∣ Γ y ∣ 2 ∣ E ∣ λ 1 l − 1 Expected((A^l)_{x,y})=\frac {|\Gamma_x||\Gamma_y|} {2|E|}\lambda_1^{l-1} Expected((Al)x,y​)=2∣E∣∣Γx​∣∣Γy​∣​λ1l−1​

• λ 1 \lambda_1 λ1​：图网络邻接矩阵的最大或主导特征值

将 A l A^l Al用 E x p e c t e d ( A l ) Expected(A^l) Expected(Al)代替，则：（PS: 这一步不知道如何得来的，还望大神指点）
S = 2 ∣ E ∣ λ 1 D − 1 ( I − β λ 1 A ) − 1 D − 1 S = 2|E|\lambda_1D^{-1}(I-\frac {\beta} {\lambda_1}A)^{-1}D^{-1} S=2∣E∣λ1​D−1(I−λ1​β​A)−1D−1

• D D D：对角矩阵， D i , i = Γ i D_{i,i}=\Gamma_i Di,i​=Γi​
• β \beta β：与 ϕ \phi ϕ有关的参数

如果删除了上式的常数因子，则可迭代计算其表达式，从而避免其矩阵的逆。
S ( t ) = β λ 1 A S ( t − 1 ) + I S(t)=\frac {\beta} {\lambda_1} A S(t-1) + I S(t)=λ1​β​AS(t−1)+I

详细过程如下：（有错误还望指出）
去掉 2 ∣ E ∣ , λ 1 , D − 1 2|E|,\lambda_1,D^{-1} 2∣E∣,λ1​,D−1后，原式变为
S = ( I − β λ 1 A ) − 1 S = (I-\frac {\beta} {\lambda_1}A)^{-1} S=(I−λ1​β​A)−1

S ( I − β λ 1 A ) = I S(I-\frac {\beta} {\lambda_1}A) = I S(I−λ1​β​A)=I

S = β λ 1 A S + I S = \frac {\beta} {\lambda_1} A S + I S=λ1​β​AS+I

对于主要特征值的求法，可采用迭代的方式进行求解
b ( t ) = A b ( t − 1 ) ∣ ∣ A b ( t − 1 ) ∣ ∣ b(t) = \frac {Ab(t-1)} {||Ab(t-1)||} b(t)=∣∣Ab(t−1)∣∣Ab(t−1)​

• b b b：长度为 ∣ V ∣ |V| ∣V∣的向量

3.2.4 Random walks (RW)

给定一个图和一个起始节点，让我们假设我们随机选择该节点的一个邻居并移动到它。然后，我们对每个到达的节点重复此过程。

定义 p x ⃗ \vec{p^x} px ​ 为从节点 x x x开始随机游走到达任何节点的概率向量，则到达每一个节点的概率可近似迭代为:
p x ⃗ ( t ) = M T p x ⃗ ( t − 1 ) \vec{p^x}(t)=M^T \vec{p^x}(t-1) px ​(t)=MTpx ​(t−1)

• M M M ：由邻接矩阵 A A A定义的转移概率矩阵，并由该矩阵进行行归一化。 M i , j = A i , j / ∑ k A i , k M_{i,j}=A{i,j}/\sum_kA_{i,k} Mi,j​=Ai,j/∑k​Ai,k​
• 初始化时，除了 p x x ⃗ ( 0 ) = 1 \vec{p^x_x}(0)=1 pxx​ ​(0)=1，其他都置为0

相似性函数为:
s ( x , y ) = p y x ⃗ s(x,y)=\vec{p_y^x} s(x,y)=pyx​ ​

3.2.5 Random walks with restart (RWR)

基于随机游动的定义的模型，其中我们选择一个节点并以概率 α α α跟随随机游动移动，或者以概率 1 − α 1-α 1−α返回起始节点。几乎与 G o o g l e ′ s Google's Google′s P a g e R a n k PageRank PageRank算法的根本相同。

定义 p x ⃗ \vec{p^x} px ​ 为从节点 x x x开始随机游走到达任何节点的概率向量，则到达每一个节点的概率可近似迭代为:
p x ⃗ ( t ) = α M T p x ⃗ ( t − 1 ) + ( 1 − α ) s x ⃗ \vec{p^x}(t)=\alpha M^T \vec{p^x}(t-1)+(1-\alpha)\vec{s^x} px ​(t)=αMTpx ​(t−1)+(1−α)sx

• M M M ：由邻接矩阵 A A A定义的转移概率矩阵，并由该矩阵进行行归一化。 M i , j = A i , j / ∑ k A i , k M_{i,j}=A{i,j}/\sum_kA_{i,k} Mi,j​=Ai,j/∑k​Ai,k​
• s x ⃗ \vec{s^x} sx ：长度为 ∣ V ∣ |V| ∣V∣的种子向量，除了 s x x ⃗ = 1 \vec{s^x_x}=1 sxx​ ​=1,其他元素均为0
• 初始化时，除了 p x x ⃗ ( 0 ) = 1 \vec{p^x_x}(0)=1 pxx​ ​(0)=1，其他都置为0

由于此度量不是对称的，故相似性函数为：
s ( x , y ) = p y x ⃗ + p x y ⃗ s(x,y)=\vec{p_y^x}+\vec{p^y_x} s(x,y)=pyx​ ​+pxy​ ​

3.2.6 Flow propagation (FP)

替代规范化可以用于邻接矩阵，可以将归一化的邻接矩阵替换为 L a p l a c i a n Laplacian Laplacian矩阵。该矩阵为：
M = D l A D r M=D^l A D^r M=DlADr

• D l D^l Dl：对角矩阵 D i , i l = 1 / ∑ j A i , j D^l_{i,i}=1/\sqrt{\sum_jA_{i,j}} Di,il​=1/∑j​Ai,j​ ​
• D r D^r Dr：对角矩阵 D i , i r = 1 / ∑ j A j , i D^r_{i,i}=1/\sqrt{\sum_jA_{j,i}} Di,ir​=1/∑j​Aj,i​ ​

3.2.7 Maximal entropy random walk (MERW)

点倾向于链接到结构化网络中的中央节点。最大熵随机游走法结合了节点的中心性以对这种行为进行建模。此方法旨在最大化步长µ的熵率，该步长定义为:
μ = lim ⁡ l → ∞ − ∑ p a t h x , y l ∈ p a t h s l p ( p a t h x , y l ) l n p ( p a t h x , y l ) l \mu=\lim_{l\rightarrow\infty}\frac {-\sum_{path^l_{x,y}\in paths^l}p(path^l_{x,y})lnp(path^l_{x,y})} {l} μ=l→∞lim​l−∑pathx,yl​∈pathsl​p(pathx,yl​)lnp(pathx,yl​)​

• p ( p a t h x , y l ) = M x , h M h , i ⋯ M i , j M j , y p(path^l_{x,y})=M_{x,h}M_{h,i} \cdots M_{i,j}M_{j,y} p(pathx,yl​)=Mx,h​Mh,i​⋯Mi,j​Mj,y​
• M i , j = A i , j λ ψ j ψ i M_{i,j}=\frac {A_{i,j}} {\lambda} \frac {\psi_j} {\psi_i} Mi,j​=λAi,j​​ψi​ψj​​
• λ \lambda λ：邻接矩阵的最大特征值
• ψ \psi ψ：特征值 λ \lambda λ对于的归一化特征向量

3.2.8 SimRank (SR)

SimRank是一种计算从节点x和y开始的两个随机游走者多久能遇到的方法。

相似性函数为:
s ( x , y ) = β ∑ i ∈ Γ x ∑ j ∈ Γ y s ( i , j ) ∣ Γ x ∣ ∣ Γ y ∣ s(x,y)=\beta \frac {\sum_{i\in\Gamma_x}\sum_{j \in \Gamma_y}s(i,j)} {|\Gamma_x||\Gamma_y|} s(x,y)=β∣Γx​∣∣Γy​∣∑i∈Γx​​∑j∈Γy​​s(i,j)​

• s ( z , z ) = 1 s(z,z)=1 s(z,z)=1
• 0 < β < 1 0<\beta<1 0<β<1 ：阻尼因子

PS: 随着无向边的数量增加，此方法变得不切实际。

3.2.9 Pseudoinverse of the Laplacian matrix (PLM)

D e f i n e Define Define： L = D − A L=D-A L=D−A

• D D D：对角矩阵， D i , i = ∣ Γ i ∣ D_{i,i}=|\Gamma_i| Di,i​=∣Γi​∣
• A A A：邻接矩阵

上述矩阵的 M o o r e − P e n r o s e Moore-Penrose Moore−Penrose伪逆记为 L + L^+ L+
求解方法：

1. L = U ∑ V T L=U \sum V^T L=U∑VT ：做SVD分解
2. L + = V ∑ + U T L^+=V\sum^+U^T L+=V∑+UT

基于内积的度量来计算相似度
s ( x , y ) = L x , y + L x , x + L y , y + s(x,y)=\frac {L^+_{x,y}} {\sqrt{L^+_{x,x}L^+_{y,y}}} s(x,y)=Lx,x+​Ly,y+​ ​Lx,y+​​

3.2.10 Average commute time (ACT)

ACT定义为从节点x开始的随机步行首次到达节点y并返回x的平均步数。
用拉普拉斯矩阵L的伪逆计算为:
n ( x , y ) = ∣ E ∣ ( L x , x + + L y , y + − 2 L x , y + ) n(x,y)=|E|(L^+_{x,x}+L^+_{y,y}-2L^+_{x,y}) n(x,y)=∣E∣(Lx,x+​+Ly,y+​−2Lx,y+​)

相似性函数为：
s ( x , y ) = 1 n ( x , y ) s(x,y)=\frac {1} {n(x,y)} s(x,y)=n(x,y)1​

3.2.11 Random forest kernel index (RFK)

根据矩阵树定理可得出相似性函数为：
S = ( I + L ) − 1 S=(I+L)^{-1} S=(I+L)−1

3.2.12 The Blondel index (BI)

此方法最初建议用来测量不同图中一对顶点的相似度。但是，它可以适合于在单个图形中工作。迭代计算为：
S ( t ) = A S ( t − 1 ) A T + A T S ( t − 1 ) A ∣ ∣ A S ( t − 1 ) A T + A T S ( t − 1 ) A ∣ ∣ F S(t)=\frac {AS(t-1)A^T+A^TS(t-1)A} {||AS(t-1)A^T+A^TS(t-1)A||_F} S(t)=∣∣AS(t−1)AT+ATS(t−1)A∣∣F​AS(t−1)AT+ATS(t−1)A​

• S ( 0 ) = I S(0)=I S(0)=I
• ∣ ∣ M m ∗ n ∣ ∣ F = ∑ i = 1 m ∑ j = 1 n ( M i , j ) 2 ||M_{m*n}||_F=\sqrt{\sum_{i=1}^m\sum_{j=1}^n(M_{i,j})^2} ∣∣Mm∗n​∣∣F​=∑i=1m​∑j=1n​(Mi,j​)2 ​

3.3 Quasi-local Approaches

3.3.1 The local path index (LPI)

基于 K a t z Katz Katz索引，但仅考虑了有限数量的路径长度。

相似度矩阵为:
S = ∑ i = 2 l β i − 2 A i S = \sum_{i=2}^l \beta^{i-2}A^i S=i=2∑l​βi−2Ai

3.3.2 Local random walks (LRW)

基于随机游走

s x , y ( t ) = ∣ Γ x ∣ 2 ∣ E ∣ p y x ⃗ ( t ) + ∣ Γ y ∣ 2 ∣ E ∣ p x y ⃗ ( t ) s^{x,y}(t)=\frac {|\Gamma_x|} {2|E|} \vec {p^x_y}(t) + \frac {|\Gamma_y|} {2|E|} \vec {p^y_x}(t) sx,y(t)=2∣E∣∣Γx​∣​pyx​ ​(t)+2∣E∣∣Γy​∣​pxy​ ​(t)

3.3.3 Superposed random walks (SRW)

s x , y ( t ) = ∑ i = 1 t （ ∣ Γ x ∣ 2 ∣ E ∣ p y x ⃗ ( t ) + ∣ Γ y ∣ 2 ∣ E ∣ p x y ⃗ ( t ) ） s^{x,y}(t)=\sum_{i=1}^t（\frac {|\Gamma_x|} {2|E|} \vec {p^x_y}(t) + \frac {|\Gamma_y|} {2|E|} \vec {p^y_x}(t)） sx,y(t)=i=1∑t​（2∣E∣∣Γx​∣​pyx​ ​(t)+2∣E∣∣Γy​∣​pxy​ ​(t)）

3.3.4 Third-order resource allocation based on common neighbor interactions (ORA-CNI)

此方法是基于常见邻居交互的资源分配的扩展，该交互还考虑了距离为三的路径。

相似性函数为:
s ( x , y ) = ∑ z ∈ Γ x ⋂ Γ y 1 ∣ Γ z ∣ + ∑ e i , j ∈ E , ∣ Γ i ∣ < ∣ Γ j ∣ , i ∈ Γ x . j ∈ Γ y ( 1 ∣ Γ i ∣ − 1 ∣ Γ j ∣ ) + β ∑ [ x , p , q , y ] ∈ p a t h s x , y 3 1 ∣ Γ p ∣ ∣ Γ q ∣ s(x,y)=\sum_{z \in \Gamma_x \bigcap \Gamma_y} \frac {1} {|\Gamma_z|}+\sum_{e_{i,j}\in E, |\Gamma_i|<|\Gamma_j|,i \in \Gamma_x. j \in \Gamma_y}(\frac {1} {|\Gamma_i|} - \frac {1} {|\Gamma_j|})+\beta \sum_{[x,p,q,y] \in paths^3_{x,y}}\frac {1} {|\Gamma_p||\Gamma_q|} s(x,y)=z∈Γx​⋂Γy​∑​∣Γz​∣1​+ei,j​∈E,∣Γi​∣<∣Γj​∣,i∈Γx​.j∈Γy​∑​(∣Γi​∣1​−∣Γj​∣1​)+β[x,p,q,y]∈pathsx,y3​∑​∣Γp​∣∣Γq​∣1​

3.3.5 FriendLink (FL)

F r i e n d L i n k FriendLink FriendLink是一种基于局部节点间路径计数的准局部度量,但是，此方法使用归一化和其他路径长度惩罚机制。

相似性函数为：
s ( x , y ) = ∑ i = 2 l 1 i − 1 ( A i ) x , y ∏ j = 2 i ( ∣ V ∣ − j ) s(x,y)=\sum_{i=2}^l \frac {1} {i-1} \frac {(A^i)_{x,y}} {\prod_{j=2}^i(|V|-j)} s(x,y)=i=2∑l​i−11​∏j=2i​(∣V∣−j)(Ai)x,y​​

3.4 Summary

1. 基于相似度的方法是链路预测中研究最多的类别，它们符合本调查的核心。这些方法通常应用于大规模网络，因此它们的时间复杂度是一个基本特征。
2. 从上述方法可以看出，大多数链接预测技术都是基于一些相关假设的启发式方法。链接预测问题的启发式性质允许使用各种方法，这些方法可能会更好或更坏，具体取决于特定的环境。
3. 由于网络的形成是一个复杂的过程，并且某些基本因素在网络之间可能会有所不同，所以不可能为所有网络设计一种比所有其他方法都更好的方法。

3.5 Experimentation

3.5.1 Datasets

• a protein-protein interaction network of budding yeast
• a neural network of Caenorhabditis elegans
• a network describing face-to-face contacts of people during the exhibition Infectious
• a frequent copurchasing network of books about US politics published
• a network of friendships among users of the hamsterster .com website
• a North American Transportation Atlas Data (NORTAD) flights from 1997 network
• a coauthorship network of scientists working on network theory and experiments

3.5.2 Evaluation and results

• G l o b a l Global Global t e c h n i q u e s techniques techniques平均取得最差的结果。它们的性能较差，以及调整其参数会严重影响间接路径，因为它们倾向于考虑过多的噪声。
• L o c a l Local Local t e c h n i q u e s techniques techniques效果很好。一些 l o c a l local local方法几次进入前五名。
• Q u a s i − l o c a l Quasi-local Quasi−local t e c h n i q u e s techniques techniques平均也取得不错的成绩。 S R W SRW SRW 技术是在我们的实验中已显示平均获得最佳结果的方法。