更改

<math> S^n=A^2+\alpha\cdot A^3+\alpha^2\cdot A^4+\cdots +\alpha^{n-2}\cdot A^n </math>

<math> S^n=A^2+\alpha\cdot A^3+\alpha^2\cdot A^4+\cdots +\alpha^{n-2}\cdot A^n </math>

随着 n 的增加，局部路径指标的计算复杂度越来越大。一般而言，考虑 n 阶路径的计算复杂度为O(N<k>^n)。但是当 n 趋于无穷大的时候，局部路径指标相当于考虑网络全部路径的Katz指标，此时计算量反而有可能下降，因为可转变为计算矩阵的逆。

随着 n 的增加，局部路径指标的计算复杂度越来越大。一般而言，考虑 n 阶路径的计算复杂度为O(N<k>^n)。但是当 n 趋于无穷大的时候，局部路径指标相当于考虑网络全部路径的Katz指标，此时计算量反而有可能下降，因为可转变为计算矩阵的逆<ref name="[10]">Linyuan Lü, Ci-Hang Jin,  Tao Zhou () [https://pattern.swarma.org/paper?id=ba461814-70a3-11ea-8026-0242ac1a0005 Similarity Index Based on Local Paths for Link Prediction of Complex Networks].</ref>。

2.Katz指标

2.Katz指标

<math>S = (I - \alpha\cdot A)^{-1} - I</math>

<math>S = (I - \alpha\cdot A)^{-1} - I</math>

显然，当参数<math>\alpha</math> 很小时，高阶路径的贡献也较小，使得 Katz 指标的预测结果接近于局部路径指标。

显然，当参数<math>\alpha</math> 很小时，高阶路径的贡献也较小，使得 Katz 指标的预测结果接近于局部路径指标<ref name="[11]">Leo Katz (1953) [https://pattern.swarma.org/paper?id=b2dee81c-70b2-11ea-b7f9-0242ac1a0005 A new status index derived from sociometric analysis].psychometrika.18.1:(39-43)</ref>。

3.LHN-II指标

3.LHN-II指标

还有相当数量的相似性指标是基于随机游走过程定义的，包括'''平均通勤时间 Average commute time''' 、'''Cos+指标'''、'''有重启的随机游走 Random walk with restart'''、'''SimRank'''指标、'''局部随机游走指标 Local random walk''' 和'''有叠加效应的随机游走指标 Superposed random walk'''等。

还有相当数量的相似性指标是基于随机游走过程定义的，包括'''平均通勤时间 Average commute time''' 、'''Cos+指标'''、'''有重启的随机游走 Random walk with restart'''、'''SimRank'''指标、'''局部随机游走指标 Local random walk''' 和'''有叠加效应的随机游走指标 Superposed random walk'''等。

1.平均通勤时间 ACT  

1.平均通勤时间 ACT <ref name="[12]">D. J. Klein,M. Randić (1993) [https://pattern.swarma.org/paper?id=b5177044-70c7-11ea-b241-0242ac1a0005 Resistance distance].journal of mathematical chemistry.12.1:(81-95)</ref>

设<math>m(x,y)</math> 为一个随机粒子从节点x到节点y平均需要走的步数，那么节点x和y的平均通勤时间定义为：<math>n(x , y) = m(x , y) + m(y , x) </math>

设<math>m(x,y)</math> 为一个随机粒子从节点x到节点y平均需要走的步数，那么节点x和y的平均通勤时间定义为：<math>n(x , y) = m(x , y) + m(y , x) </math>

<math>s_{xy}^{ACT}=\frac{1}{l^+_{xx} +l^+_{yy} - 2l^+_{xy}}</math>

<math>s_{xy}^{ACT}=\frac{1}{l^+_{xx} +l^+_{yy} - 2l^+_{xy}}</math>

2.余弦相似性指标 Cos+指标

2.余弦相似性指标 Cos+指标<ref name="13">Fouss F, Pirotte A, Renders J M (2007) [https://pattern.swarma.org/paper?id=f3ce12c4-70c8-11ea-8ff9-0242ac1a0005 Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation].IEEE Transactions on knowledge and data engineering.19.(355-369)</ref>

在由向量<math>v_x = \Lambda ^{1/2}U^{T}e_{x}</math>展开的欧式空间内，<math>L^+ </math>中的元素<math>l^{+}_{xy}</math>可表示为两向量<math>v_x</math>和<math>v_y</math>的内积，即<math> l^{+}_{xy} = v_{x}^{T} v_y</math>，其中<math>U</math>是一个标准正交矩阵，由<math>L^+</math>特征向量按照对应的特征根从大到小排列，<math>\Lambda</math>为以特征根为对角元素的对角矩阵，<math>e_{x}</math> 表示一个一维向量且只有第x个元素为1，其他都为0。由此定义余弦相似性如下：

在由向量<math>v_x = \Lambda ^{1/2}U^{T}e_{x}</math>展开的欧式空间内，<math>L^+ </math>中的元素<math>l^{+}_{xy}</math>可表示为两向量<math>v_x</math>和<math>v_y</math>的内积，即<math> l^{+}_{xy} = v_{x}^{T} v_y</math>，其中<math>U</math>是一个标准正交矩阵，由<math>L^+</math>特征向量按照对应的特征根从大到小排列，<math>\Lambda</math>为以特征根为对角元素的对角矩阵，<math>e_{x}</math> 表示一个一维向量且只有第x个元素为1，其他都为0。由此定义余弦相似性如下：

s_{xy}^{cos+}=cos(x,y)^+=\frac{l_{xy}^+}{\sqrt{l^+_{xx} \cdot l^+_{yy}}}

s_{xy}^{cos+}=cos(x,y)^+=\frac{l_{xy}^+}{\sqrt{l^+_{xx} \cdot l^+_{yy}}}

3.重启的随机游走 RWR

3.重启的随机游走 RWR<ref name="[14]">Brin, S, Page, L (1998) [https://pattern.swarma.org/paper?id=15405998-70ca-11ea-b1b5-0242ac1a0005 The anatomy of a large-scale hypertextual web search engine].</ref>

这个指标可以看成是PageRank 算法的拓展应用。它假设随机游走粒子在每走一步的时候都以一定概率返回初始位置。设粒子返回概率为 1-c，<math>P</math> 为网络的马尔科夫概率转移矩阵，其元素 <math>P_{xy} = a_{xy}/k_{x} </math>表示节点x处的粒子下一步走到节点y的概率。其中如果节点x和节点y相连，则<math>a_{xy}=1</math>，否则<math>a_{xy}=0</math>。某一粒子初始时刻在节点x处，那么t+1时刻该粒子到达网络各个节点的概率向量为

这个指标可以看成是PageRank 算法的拓展应用。它假设随机游走粒子在每走一步的时候都以一定概率返回初始位置。设粒子返回概率为 1-c，<math>P</math> 为网络的马尔科夫概率转移矩阵，其元素 <math>P_{xy} = a_{xy}/k_{x} </math>表示节点x处的粒子下一步走到节点y的概率。其中如果节点x和节点y相连，则<math>a_{xy}=1</math>，否则<math>a_{xy}=0</math>。某一粒子初始时刻在节点x处，那么t+1时刻该粒子到达网络各个节点的概率向量为

<math>s_{xy}^{RWR} = q_{xy} + q_{yx} </math>

<math>s_{xy}^{RWR} = q_{xy} + q_{yx} </math>

4.SimRank指标 SimR

4.SimRank指标 SimR<ref name="[14]">Jeh G, Widom J. SimRank (2002) [https://pattern.swarma.org/paper?id=593e78e0-70cb-11ea-9743-0242ac1a0005 a measure of structural-context similarity].(538-543)</ref>

它的基本假设是，如果两节点所连接的节点相似，那么这两个节点就相似。其自洽定义式为

它的基本假设是，如果两节点所连接的节点相似，那么这两个节点就相似。其自洽定义式为

SimR指标同时考虑了结构等价和一般等价。当节点x的邻居z同时也是节点y的邻居时，该指标考虑了结构等价；当节点x不等于节点y时，该指标概率了一般等价。可以证明，SimR指标可以用来描述两个分别从节点x和y出发的粒子平均过多久会相遇。

SimR指标同时考虑了结构等价和一般等价。当节点x的邻居z同时也是节点y的邻居时，该指标考虑了结构等价；当节点x不等于节点y时，该指标概率了一般等价。可以证明，SimR指标可以用来描述两个分别从节点x和y出发的粒子平均过多久会相遇。

5.局部随机游走指标 LRW

5.局部随机游走指标 LRW<ref name="[15]">Weiping Liu,Linyuan Lu (2010) [https://pattern.swarma.org/paper?id=98d1a08e-70eb-11ea-a520-0242ac1a0005 Link Prediction Based on Local Random Walk].arXiv:1001.2467.89.(58007)</ref>

上述4种随机游走指标是基于全局的随机游走，这类指标往往计算复杂度很高，因此很难在大规模网络上应用。刘伟平和吕琳媛提出了一种基于网络局部随机游走的相似性指标LRW，它只考虑有限步数的随机游走过程。一个粒子 t 时刻从节点x出发，定义<math>π_{xy} (t) </math>为 t+1 时刻这个粒子正好走到节点y的概率，那么可得到系统演化方程：

上述4种随机游走指标是基于全局的随机游走，这类指标往往计算复杂度很高，因此很难在大规模网络上应用。刘伟平和吕琳媛提出了一种基于网络局部随机游走的相似性指标LRW，它只考虑有限步数的随机游走过程。一个粒子 t 时刻从节点x出发，定义<math>π_{xy} (t) </math>为 t+1 时刻这个粒子正好走到节点y的概率，那么可得到系统演化方程：

<math>s_{xy}^{LRW} = q_{xy} + q_{yx}</math>

<math>s_{xy}^{LRW} = q_{xy} + q_{yx}</math>

6.叠加的局部随机游走指标 SRW

6.叠加的局部随机游走指标 SRW<ref name="[15]">Weiping Liu,Linyuan Lu (2010) [https://pattern.swarma.org/paper?id=98d1a08e-70eb-11ea-a520-0242ac1a0005 Link Prediction Based on Local Random Walk].arXiv:1001.2467.89.(58007)</ref>

这个指标给邻近目标节点的点更多的机会与目标节点相连，充分考虑了很多真实网络连接上的局域性特点，它是在LRW的基础上，将t步及其以前的结果加总，便得到SRW的值，即：

这个指标给邻近目标节点的点更多的机会与目标节点相连，充分考虑了很多真实网络连接上的局域性特点，它是在LRW的基础上，将t步及其以前的结果加总，便得到SRW的值，即：