基于边

基于边的方法主要目的是预测节点与节点之间的边是否有连接。最简单的做法是对每个节点对进行评分，评分越高则越可能有边相连接（如距离的相反数）。而具体基于边的特征则包括：基于距离的特征（Distance based features）；局部相邻重叠（Local neighborhood overlap）；全局相邻重叠（Global neighborhood overlap）。

a. 基于距离的特征

此方法直接使用两个节点之间的最短路径长度，如下图所示，点与点之间的距离直接用途径边的条数进行表示。

这种方法简单粗暴，但没有考虑到两个节点之间的共同相邻节点情况，如 B-H 的共同相邻结点有 C 和 D；B-E 只有一个共同相邻节点，通过此方法看不出差距。

b. 邻居局部重合度

针对前面基于距离特征方法的缺陷，这里考虑了两个节点之间共同的相邻结点个数。

以上图为例，这里分别介绍三个邻居局部重合度指标：

• Common neighbors（公共邻居）：
  ∣ N ( v 1 ) ∩ N ( v 2 ) ∣ \left|N\left(v_{1}\right) \cap N\left(v_{2}\right)\right| ∣N(v1​)∩N(v2​)∣

例子: ∣ N ( A ) ∩ N ( B ) ∣ = ∣ { C } ∣ = 1 |N(A) \cap N(B)|=|\{C\}|=1 ∣N(A)∩N(B)∣=∣{C}∣=1。

• Jaccard’s coefficient（公共邻居 / 所有邻居）：
  ∣ N ( v 1 ) ∩ N ( v 2 ) ∣ ∣ N ( v 1 ) ∪ N ( v 2 ) ∣ \frac{\left|N\left(v_{1}\right) \cap N\left(v_{2}\right)\right|}{\left|N\left(v_{1}\right) \cup N\left(v_{2}\right)\right|} ∣N(v1​)∪N(v2​)∣∣N(v1​)∩N(v2​)∣​

例子: ∣ N ( A ) ∩ N ( B ) ∣ ∣ N ( A ) ∪ N ( B ) ∣ = ∣ { C ∣ ∣ ∣ { C , D } ∣ = 1 2 \frac{|N(A) \cap N(B)|}{|N(A) \cup N(B)|}=\frac{\mid\{C||}{|\{C, D\}|}=\frac{1}{2} ∣N(A)∪N(B)∣∣N(A)∩N(B)∣​=∣{C,D}∣∣{C∣∣​=21​。

• Adamic Adar index：
  ∑ u ∈ N ( v 1 ) ∩ N ( v 2 ) 1 log ⁡ ( k u ) \sum_{u \in N\left(v_{1}\right) \cap N\left(v_{2}\right)} \frac{1}{\log \left(k_{u}\right)} u∈N(v1​)∩N(v2​)∑​log(ku​)1​

例子: 1 log ⁡ ( k C ) = 1 log ⁡ 4 \frac{1}{\log \left(k_{C}\right)}=\frac{1}{\log 4} log(kC​)1​=log41​（ k C k_{C} kC​为C点的度）。该值将公共节点的度取log再取倒数，这个值越大，说明公共节点的度越小，也即对这两个节点中越重要。因为这些low-degree的节点能够比high-degree的节点提供更多信息，这点在文本分类中思想也有体现，譬如经典的TF-IDF，给予频率较少的词更大权重以区分不同词的重要性。

这种方法野还是有一个问题：当两个节点之间没有共同的相邻结点时，对应的指标值为0。如示例图中的节点A与E之间就没有共同的邻居。全局重合度很好的解决了上述问题。

c. 全局重合度

全局重合度使用了全局图结构对两个节点进行评分。这里考虑Katz index。

Katz index：计算遍历两个节点所有路径的总距离，这里的路可以是任意长度，且不需要是最短的路。那么要如何计算两个节点所有路径的总距离呢？这里使用邻接矩阵的幂进行计算。

令 P u v ( K ) P_{uv}^{(K)} Puv(K)​为： u , v u, v u,v之间，长度为 K K K的所有路径之和，假设邻接矩阵为 A k A^k Ak，则很容易证明 P u v ( K ) = A K P_{uv}^{(K)}=A^K Puv(K)​=AK。其实从定义可以很容易看出，矩阵乘法正好是把中继节点全部遍历求和：

因此可以得到，Katz index的计算公式（这里我们为每条路径上赋予一个权重 β \beta β，其为标量）：
S Katz  [ u , v ] = ∑ i = 1 ∞ β i A i [ u , v ] S_{\text {Katz }}[u, v]=\sum_{i=1}^{\infty} \beta^{i} A^{i}[u, v] SKatz ​[u,v]=i=1∑∞​βiAi[u,v]
其中 β \beta β 则是我们设定的描述长短路不同的权重，譬如我们希望长路的权重低一些，则设置 β < 1 \beta<1 β<1 。

下面进行求解，这里需要假设 A A A最大的特征值 λ 1 < 1 \lambda_{1}<1 λ1​<1 以及 ( I − A ) (I-A) (I−A) 非奇异，其中 I I I 是单位矩阵，求解方法很简单，设 s n = ∑ i = 0 n A i s_{n}=\sum_{i=0}^{n} A^{i} sn​=∑i=0n​Ai,则
A s n = A ∑ i = 0 n A i = ∑ i = 1 n + 1 A i A s_{n}=A \sum_{i=0}^{n} A^{i}=\sum_{i=1}^{n+1} A_{i} Asn​=Ai=0∑n​Ai=i=1∑n+1​Ai​
进而设
s n − A s n = ∑ i = 0 n A i − ∑ i = 1 n + 1 A i s n ( I − A ) = I − A n + 1 s n = ( I − A n + 1 ) ( I − A ) − 1 \begin{aligned} &s_{n}-A s_{n}=\sum_{i=0}^{n} A^{i}-\sum_{i=1}^{n+1} A^{i} \\ &s_{n}(I-A)=I-A^{n+1} \\ &s_{n}=\left(I-A^{n+1}\right)(I-A)^{-1} \end{aligned} ​sn​−Asn​=i=0∑n​Ai−i=1∑n+1​Aisn​(I−A)=I−An+1sn​=(I−An+1)(I−A)−1​
因为 λ 1 < 1 \lambda_{1}<1 λ1​<1, 从而 lim ⁡ n → ∞ A n = 0 \lim _{n \rightarrow \infty} A^{n}=0 limn→∞​An=0 以及
lim ⁡ n → ∞ s n = lim ⁡ n → ∞ ( I − A n + 1 ) ( I − A ) − 1 = I ( I − A ) − 1 = ( I − A ) − 1 \lim_{n \rightarrow \infty} s_{n}=\lim_{n \rightarrow \infty}\left(I-A^{n+1}\right)(I-A)^{-1}=I(I-A)^{-1}=(I-A)^{-1} n→∞lim​sn​=n→∞lim​(I−An+1)(I−A)−1=I(I−A)−1=(I−A)−1
所以Katze index最后在求解的时候其实求的是
S K a t z = ( I − β A ) − 1 − I S_{K a t z}=(I-\beta A)^{-1}-I SKatz​=(I−βA)−1−I